# Rota's basis conjecture

 Importance: High ✭✭✭
 Author(s): Rota, Gian-Carlo
 Subject: Combinatorics » Matrices
 Keywords: base latin square linear algebra matroid transversal
 Posted by: mdevos on: October 6th, 2007
Conjecture   Let be a vector space of dimension and let be bases. Then there exist disjoint transversals of each of which is a base.

This very pretty conjecture of Rota has a number of interesting extensions. One (obvious) extension is to matroids, and indeed, Rota conjectured this generalization (just replace the vector space of dimension by a matroid of rank ). This generalization has received some recent attention: Geelen and Humphries [GH] proved the special case when is a paving matroid, Geelen and Webb [GW] proved that in general there exist disjoint transversals which are bases, and Aharoni and Berger [AB] used their beautiful "intersection of a matroid and a simplicial complex" theorem to prove that the union of the bases can be partitioned into partial independent transversals. Another generalization of Rota's basis conjecture is the following.

Conjecture  (Kahn)   Let be a vector space of dimension and for and let be a basis. Then we may choose a vector from each basis so that in the matrix , every row and every column is a basis.

To the best of my (M. DeVos') knowledge, this conjecture may generalize to matroids as well. There is another conjecture which implies Rota's basis conjecture which is far less obvious. In fact, Rota's conjecture (for even and characteristic zero) is implied by Alon and Tarsi's Even vs. odd latin squares conjecture. This implication was first discovered by Rota and Huang [RH] (Rota had himself made another conjecture equivalent to that of Alon and Tarsi), and a very transparent proof of this fact based on a polynomial identity is given by Shmuel Onn [O].

Thanks to this last implication, partial results on the Alon-Tarsi conjecture show that Rota's basis conjecture holds whenever has the form or where is an odd prime [D1], [D2], [Z].

In August 2020, an asymptotic solution to the matroid's generalization of the conjecture was announced by Alexey Pokrovskiy [P].

## Bibliography

[AB] R. Aharoni, E. Berger, The intersection of a matroid and a simplicial complex. Trans. Amer. Math. Soc. 358 (2006), no. 11, 4895--4917 MathSciNet.

[AT] N. Alon, M. Tarsi, Coloring and Orientations of Graphs. Combinatorica 12, 125-143, 1992 MathSciNet

[D1] A. Drisko, On the number of even and odd Latin squares of order , Adv. Math. 128 (1997), no. 1, 20--35. MathSciNet

[D2] A. Drisko, Proof of the Alon-Tarsi conjecture for . Electron. J. Combin. 5 (1998) MathSciNet.

[GH] J. Geelen, and P. J. Humphries, Rota's basis conjecture for paving matroids. SIAM J. Discrete Math. 20 (2006), no. 4, 1042--1045 MathSciNet.

[GW] J. Geelen, and K. Webb, On Rota's basis conjecture

*[HR] R. Huang and G-C Rota, On the relations of various conjectures on Latin squares and straightening coefficients. Discrete Math. 128 (1994), no. 1-3, 225--236. MathSciNet.

[O] S. Onn, A colorful determinantal identity, a conjecture of Rota, and Latin squares. Amer. Math. Monthly 104 (1997), no. 2, 156--159. MathSciNet.

[P] A. Pokrovskiy, Rota’s Basis Conjecture holds asymptotically arXiv e-prints.

[W] M. Wild, On Rota's problem about bases in a rank matroid. Adv. Math. 108 (1994), no. 2, 336--345. MathSciNet.

[Z] P. Zappa, The Cayley determinant of the determinant tensor and the Alon-Tarsi Conjecture, Adv. Appl. Math. 19 (1997), 31--44.

* indicates original appearance(s) of problem.

### Rota's Basis Conjecture is still open

Dear Jon Noel, I believe that the following statement that you added to this posting on Aug. 28, 2013 is incorrect:

“It has been announced that Rota's Basis Conjecture has been proved by Geelen, Gerards and Whittle (2013). The proof reportedly applies a Theory of Matroid Minors developed by the authors.”

The announcement you referred to is actually regarding a different famous conjecture, called Rota’s conjecture, about forbidden minors of matroids. Besides the common author, the latter conjecture has nothing to do with Rota's Basis Conjecture which is, as far as I am concerned, still open.

Consequently I’m removing your statement and returning the status of the problem to unsolved.

### Oops

My mistake. Thanks.