If [@conj-doublecover] is true, then 3 common bases will be enough to cover $E$.
# Known results
Let $\beta(M)$ be the covering number of matroid $M$. Given two matroids $M_1,M_2$ on the same ground set, $\beta(M_1\cap M_2)$ is the minimum number of common independent sets needed to cover the ground set.
[@conj-doublecover] is basically asking for $\beta(M_1\cap M_2)$ when the ground set $E$ is partitioned into 2 common bases of $M_1$ and $M_2$.
## Results and conjectures on $\beta(M_1\cap M_2)$
One can see that $\beta(M_1\cap M_2)\geq \min \set{\beta(M_1),\beta(M_2)}$. Aharoni and Berger showed that $\beta(M_1\cap M_2)\leq 2 \max \set{\beta(M_1),\beta(M_2)}$
::: {.Conjecture title="Aharoni and Berger"}
Let $M_1$ and $M_2$ be two matroids on the same ground set.
1. If $\beta(M_1)\neq \beta(M_2)$, then $\beta(M_1\cap M_2)=\max \set{\beta(M_1),\beta(M_2)}$.
2. If $\beta(M_1)= \beta(M_2)$, then $\beta(M_1\cap M_2)\leq \max \set{\beta(M_1),\beta(M_2)}+1$.
- If $\beta(M_1)=\beta(M_2)=2$ then $\beta(M_1\cap M_2)=3$.^[Note that this case does not give an answer to [@prob-rainbowbasecover] since the covering in $\beta(M_1\cap M_2)$ uses common independent sets instead of common bases.]
See [@berczi_partitioning_2024] for refs. Bérczi and Schwarcz generalized SBO using the following definition.
::: {.Definition title="strongly base reorderable"}
A matroid is called **strongly base reorderable**(SBRO) if for any pair $A,B$ of bases, there exists bases $A',B'$ and a bijection $\phi:A'\setminus B'\to B'\setminus A'$ such that $A'\cap B'=A\cap B,A'\cup B'=A\cup B$, and $(A'\setminus X)\cup \phi(X)$ is a basis for every $X\subset A'\setminus B'$.
:::
::: Lemma
The class of SRBO matroids is complete(closed under taking minors, duals, direct sums, truncations and induction by directed graphs).
:::
They also showed that SBRO is sufficient for $\beta(M_1\cap M_2)=\max \set{\beta(M_1),\beta(M_2)}$.
::: Theorem
Let $M_1$ and $M_2$ be strongly base reorderable matroids on the same ground set.
Then $\beta(M_1\cap M_2)= \max \set{\beta(M_1),\beta(M_2)}$.
:::
## Circuit cover
Let $M=(E,\mathcal B)$ be a matroid and let $A,B\in \mathcal B$ be two bases of $M$.
Given a graph $G=(A\Delta B, F)$, we say $G$ covers a circuit $C\subset A\Delta B$ if the induced subgraph $G[C]$ contains an edge.
For a class of circuits $\mathcal C$ in $A\Delta B$, we say $G$ covers $\mathcal C$ if $G$ covers every circuit in $\mathcal C$.
::: {.Conjecture #conj-alterpath}
Let $A,B$ be bases of a matroid $M$. Then there exists a path that alternates between $A\setminus B$ and $B\setminus A$ and covers $\mathcal C[A\cup B]$.
:::
Bérczi and Schwarcz [@berczi_partitioning_2024] verified this conjecture for graphic matroids, paving matroids and spikes. They also showed an useful lemma:
::: {.Lemma title="informal" #lem-reduction}
To verify [@conj-alterpath] for a minor closed class of matroids, one only need to consider matroids in this class whose ground set can be partitioned into two disjoint bases.
:::
# [@conj-alterpath] on cographic matroid
::: Lemma
[@conj-alterpath] holds on cographic matroids.
:::
::: Proof
By [@lem-reduction] it suffices to show the following: Let $A,B$ be two spanning trees on vertex set $V$. One can find a sequence of edges in $A$ and $B$ such that
1. no consecutive edges belong to $A$ or $B$, and that
2. every cut in $(V,A\cup B)$ contains some consecutive edge pair in the sequence.
We prove by induction on $|V|$.
- If $|V|=2$, there is only one non-empty cut.
- Suppose that the lemma holds for $|V|<k$. Let $G=(V,A\cup B)$ be the union of two spanning trees on $k$ vertices. The average degree of $G$ is $4-4/k$ and the degree of any vertex must be at least 2. Thus there is always a vertex $v$ with $\deg(v)\in \set{2,3}$.
- If $\deg(v)=2$, then $v$ must be a leaf in both spanning trees, so $G-v$ is the union of two spanning trees. Let $a,b$ be the edges incident to $v$ in $G$. By induction hypothesis there is a desired edge sequence $\mathcal S$ for the graph $G-v$. We append $a,b$ (or $b,a$, depending on which tree the last element of $\mathcal S$ belongs to) to $\mathcal S$. Then the only cut that is not covered by $\mathcal S$ is $\delta(v)$, which contains the pair $a,b.$
- If $\deg(v)=3$, then assume $v$ is a leaf in $A$ and a deg-2 vertex in $B$. Let $a,b_1,b_2$ be the edges incident to $v$ and let $x,y$ be the neighbors of $v$ in $B$. We construct a new graph $G'$ by deleting $v$ from $G$ and adding a new edge $d=(x,y)$. Then $G'$ is the union of two spanning trees and there is a desired sequence $\mathcal S'$ for $G'$. We construct a new sequence $\mathcal S$ by replacing $d$ in $\mathcal S'$ with 3 edges $b_1,a,b_2$. For $X\subsetneq V\setminus \set{v}$, the cut $\delta(X)$ is always covered by $\mathcal S'$ but possibly use $d$. However, any cut separating $x$ and $y$ must contain $b_1$ or $b_2$ in $G$, which keeps $\mathcal S$ feasible. The remaining case is $\delta(v)$ which is covered by $b_1,a,b_2$.
