rainbow_base_cover/notes/main.md

title

title
Matroid Rainbow Base Cover

This problem is proposed in [@emlektabla16_2024].

Let M=(E,\mathcal B) be a rank-r matroid whose ground set decomposes into two disjoint bases. Furthermore, assume that E is colored by r colors, each color appearing exactly twice. A basis of M is called rainbow if it does not contain two elements of the same color.

::: {.Problem #prob-rainbowbasecover} What is the minimum number of rainbow bases needed to cover E? :::

Kristóf Bérczi conjectured the minimum number is 3.

Currently known bounds:

• upperbound: \floor{\log_2 |E|}+1 by matroid intersection;
• lowerbound: 3 on graphic matroid of K_4.

::: {.Conjecture #conj-doublecover} Let M_1 and M_2 be two matroid on the same ground set E. Assume that E decomposes into two bases in both of them. Then M_1 and M_2 has four common bases (allow repetition) that cover each element exactly twice. :::

Let M_1 be the partition matroid of colors and let M_2 be M. 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. :::

Cases that have been verified:

• 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.]
• If \beta(M_1)=2,\beta(M_2)=3, then \beta(M_1\cap M_2)\leq 4.
• If \beta(M_1)=2,\beta(M_2)=k\geq 4, then \beta(M_1\cap M_2)\leq 2\ceil{k/2}+2.

::: {.Theorem title="Davies and McDiarmid"} Let M_1 and M_2 be strongly base orderable matroids on the same ground set. Then \beta(M_1\cap M_2)= \max \set{\beta(M_1),\beta(M_2)}. :::

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. :::

Common base cover