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.
