Rota's conjecture on disjoint bases

From Egres Open
Jump to: navigation, search

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]?


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

Scrambled Rota conjecture

See also

Rota's conjecture at the Open Problem Garden, Polymath page


  1. R. Huang, G.-C. Rota, On the relations of various conjectures on Latin squares and straightening coefficients (1994), DOI link
  2. J. Geelen, P.J. Humphries, Rota's basis conjecture for paving matroids, SIAM J. Discrete Math. 20 (2006), 1042-1045. DOI link, Citeseer link
  3. J. Geelen, K. Webb, On Rota's basis conjecture, SIAM J. Discrete Math. 21 (2007), 802-804. DOI link
  4. M. Bucić, M. Kwan, A. Pokrovskiy, B. Sudakov, Halfway to Rota’s basis conjecture (2018), arXiv link
  5. R. Aharoni, E. Berger, The intersection of a matroid and a simplicial complex, Trans. Amer. Math. Soc. 358 (2006), 4895-4917. Journal link