# Upper bound on common independent set cover

For a loopless matroid [math]M=(S,r)[/math], let [math]\Delta(M)=\max_{X\subseteq S} |X|/r(X)[/math]. Let [math]M_1=(S,r_1)[/math] and [math]M_2=(S,r_2)[/math] be two arbitrary loopless matroids on *S*. Is it true that *S* can be partitioned into [math]\lceil\max\{\Delta(M_1),\Delta(M_2)\}\rceil+1[/math] common independent sets?

## Remarks

This conjecture is due to Aharoni and Berger; they also proposed a weaker version with a bound of [math]\Delta(M_1)+\Delta(M_2)[/math]. In ^{[1]}, they proved the fractional counterpart of the conjecture with bound [math]\max\{\Delta(M_1),\Delta(M_2)\}[/math], as well as the following approximate version of the conjecture:

**Theorem ^{[1]}.** Given two loopless matroids [math]M_1=(S,r_1)[/math] and [math]M_2=(S,r_2)[/math],

*S*can be partitioned into [math]2 \max\{\Delta(M_1),\Delta(M_2)\}[/math] common independent sets.

The conjecture was verified for the case [math]\Delta(M_1)\leq 2, \Delta(M_2)\leq 3[/math] in ^{[2]}.
The standard example for the necessity of +1 is the following: [math]M_1[/math] is the cycle matroid of [math]K_4[/math], and [math]M_2[/math] is the partition matroid of rank 3 whose partition classes are the pairs of independent edges. Some related results and conjectures can be found in the paper of Aharoni and Hallufgil ^{[3]}. See also the open question Edge covering number of 2-poymatroids.

## References

- ↑
^{1.0}^{1.1}R. Aharoni, E. Berger,*The intersection of a matroid and a simplicial complex*, Trans. Amer. Math. Soc. 358 (2006), 4895-4917. Journal link. Citeseer link. - ↑ R. Aharoni, E. Berger, R. Ziv,
*The edge covering number of the intersection of two matroids*, DOI link - ↑ R.Aharoni, E. Hallufgil,
*Coloring by two-way independent sets*, DOI link.