Rota's conjecture on disjoint bases
Let [math]M[/math] be a matroid of rank n whose ground set S can be partitioned into n disjoint bases [math]B_1,\dots,B_n[/math]. Is it true that [math]B_1,\dots,B_n[/math] always have n disjoint transversals that are bases of [math]M[/math]?
Remarks
This conjecture was made by Rota in 1989, see [1]. Geelen and Humphries [2] proved it for paving matroids.
For general matroids, Geelen and Webb [3] proved that [math]B_1,\dots,B_n[/math] always have [math]\Omega(\sqrt{n})[/math] disjoint transversals that are bases. This was recently improved to [math](1/2 − o(1))n[/math] by Bucić, Kwan, Pokrovskiy, and Sudakov [4]. On the other hand, it follows from the results of Aharoni and Berger [5] that S can be partitioned into 2n common independent sets.
Related questions
See also
Rota's conjecture at the Open Problem Garden, Polymath page
References
- ↑ R. Huang, G.-C. Rota, On the relations of various conjectures on Latin squares and straightening coefficients (1994), DOI link
- ↑ J. Geelen, P.J. Humphries, Rota's basis conjecture for paving matroids, SIAM J. Discrete Math. 20 (2006), 1042-1045. DOI link, Citeseer link
- ↑ J. Geelen, K. Webb, On Rota's basis conjecture, SIAM J. Discrete Math. 21 (2007), 802-804. DOI link
- ↑ M. Bucić, M. Kwan, A. Pokrovskiy, B. Sudakov, Halfway to Rota’s basis conjecture (2018), arXiv link
- ↑ R. Aharoni, E. Berger, The intersection of a matroid and a simplicial complex, Trans. Amer. Math. Soc. 358 (2006), 4895-4917. Journal link
