# Upper bound on common independent set cover

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

## Remarks

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

Theorem [1]. Given two loopless matroids $M_1=(S,r_1)$ and $M_2=(S,r_2)$, S can be partitioned into $2 \max\{\Delta(M_1),\Delta(M_2)\}$ common independent sets.

The conjecture was verified for the case $\Delta(M_1)\leq 2, \Delta(M_2)\leq 3$ in [2]. The standard example for the necessity of +1 is the following: $M_1$ is the cycle matroid of $K_4$, and $M_2$ 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. 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.
2. R. Aharoni, E. Berger, R. Ziv, The edge covering number of the intersection of two matroids, DOI link
3. R.Aharoni, E. Hallufgil, Coloring by two-way independent sets, DOI link.