Rota's conjecture

The objective of this Polymath project is to prove

Rota's Basis Conjecture: if [math]\displaystyle{ B_1,\dots,B_n }[/math] are [math]\displaystyle{ n }[/math] bases of an [math]\displaystyle{ n }[/math]-dimensional vector space [math]\displaystyle{ V }[/math] (not necessarily distinct or disjoint), then there exists an [math]\displaystyle{ n \times n }[/math] grid of vectors [math]\displaystyle{ (v_{ij}) }[/math] such that

1. the [math]\displaystyle{ n }[/math] vectors in row [math]\displaystyle{ i }[/math] are the members of the [math]\displaystyle{ i^{th} }[/math] basis [math]\displaystyle{ B_i }[/math] (in some order), and

2. in each column of the matrix, the [math]\displaystyle{ n }[/math] vectors in that column form a basis of [math]\displaystyle{ V }[/math].

Definitions

The statement of Rota's Basis Conjecture is elementary enough that definitions are not necessary, but we present here some definitions that are used below.

A matroid is a finite set [math]\displaystyle{ E }[/math] together with a non-empty family ℐ of subsets of [math]\displaystyle{ E }[/math] (called independent sets) such that

1. if [math]\displaystyle{ J }[/math] ∈ ℐ and [math]\displaystyle{ I }[/math] ⊆ [math]\displaystyle{ J }[/math] then [math]\displaystyle{ I }[/math] ∈ ℐ, and

2. if [math]\displaystyle{ I, J }[/math] ∈ ℐ and [math]\displaystyle{ |I| < |J| }[/math] then there exists [math]\displaystyle{ x }[/math] ∈ [math]\displaystyle{ J }[/math] such that [math]\displaystyle{ I ∪ {x} }[/math] ∈ ℐ.

A maximal independent set of a matroid is called a basis and it is a theorem that bases all have the same cardinality; this cardinality is the rank of the matroid.

A matroid is strongly base-orderable if, for any two bases [math]\displaystyle{ B }[/math]₁ and [math]\displaystyle{ B }[/math]₂, there exists a bijection [math]\displaystyle{ f : B }[/math]₁ → [math]\displaystyle{ B }[/math]₂ such that for every subset [math]\displaystyle{ S ⊆ B }[/math]₁, both [math]\displaystyle{ B }[/math]₁ \ [math]\displaystyle{ S ∪ f(S) }[/math] and [math]\displaystyle{ B }[/math]₂ \ [math]\displaystyle{ f(S) ∪ S }[/math] are bases. The definition of a base-orderable matroid is the same except that the condition is required to hold only for singleton sets [math]\displaystyle{ S }[/math] (so in particular, a strongly base-orderable matroid is base-orderable).

A minimal dependent set in a matroid is called a circuit.

A Latin square is an [math]\displaystyle{ n × n }[/math] grid of positive integers such that every row and every column is a permutation of the numbers from 1 to [math]\displaystyle{ n }[/math]. The sign (respectively, the row-sign) of a Latin square is the product of the signs of the permutations of the all the rows and all the columns (respectively, of all the rows) and the Latin square is called even or odd (respectively, row-even or row-odd) according to whether its sign is +1 or –1.

Partial results

For a positive integer [math]\displaystyle{ n }[/math], let AT([math]\displaystyle{ n }[/math]) (the Alon–Tarsi constant) denote the number of even [math]\displaystyle{ n × n }[/math] Latin squares minus the number of odd [math]\displaystyle{ n × n }[/math] Latin squares. Then the Alon–Tarsi Conjecture states that AT([math]\displaystyle{ n }[/math]) ≠ 0 for all even [math]\displaystyle{ n }[/math]. (It is easy to show that AT([math]\displaystyle{ n }[/math]) = 0 for odd [math]\displaystyle{ n }[/math].) We can simultaneously replace "even" with "row-even" and "odd" with "row-odd"; the resulting conjecture has been proved by Huang and Rota to be equivalent to the Alon–Tarsi Conjecture. There is a close relationship between the Alon–Tarsi Conjecture and RBC.

Theorem 1 (Huang and Rota). If AT([math]\displaystyle{ n }[/math]) ≠ 0 in a field [math]\displaystyle{ F }[/math], then RBC holds for [math]\displaystyle{ n }[/math]-dimensional vector spaces over [math]\displaystyle{ F }[/math].

Some of the strongest partial results for RBC are really partial results for the Alon–Tarsi Conjecture. In particular we have the following.

Theorem 2 (Drisko). If [math]\displaystyle{ p }[/math] is an odd prime, then AT([math]\displaystyle{ p+1 }[/math]) ≡ (–1)^{[math]\displaystyle{ (p+1)/2 }[/math]} [math]\displaystyle{ p }[/math]² modulo [math]\displaystyle{ p }[/math]³.

Theorem 3 (Glynn). If [math]\displaystyle{ p }[/math] is an odd prime, then AT([math]\displaystyle{ p-1 }[/math]) ≡ (–1)^{[math]\displaystyle{ (p-1)/2 }[/math]} modulo [math]\displaystyle{ p }[/math].

It follows that RBC is true over a field of characteristic zero in even dimensions [math]\displaystyle{ n ≤ 24 }[/math].

RBC has also been proved for certain special classes of matroids.

Theorem 4 (Wild). RBC is true for strongly base-orderable matroids.

Theorem 5 (Geelen–Humphries). RBC is true for paving matroids.

Discussion

• Proposal on MathOverflow (Feb 15, 2016)
• Rota’s Basis Conjecture: Polymath 12? (Feb 23, 2017)

References

• [AB2006] The intersection of a matroid and a simplicial complex, Ron Aharoni and Eli Burger, Trans. Amer. Math. Soc. 358 (2006), 4895–4917.
• [AK2014] A weak version of Rota's basis conjecture for odd dimensions, Ron Aharoni and Daniel Kotlar, SIAM J. Discrete Math. 28 (2014), 385–393.
• [BD2015] An online version of Rota's basis conjecture, G. P. Bollen and J. Draisma, J. Algebraic Combin. 41 (2015), 1001–1012.
• [Chan1995] An exchange property of matroid, Wendy Chan, Discrete Math. 146 (1995), 299–302.
• [Chow1995] On the Dinitz conjecture and related conjectures, Timothy Chow, Disc. Math. 145 (1995), 73–82.
• [C2009] Reduction of Rota's basis conjecture to a conjecture on three bases, Timothy Chow, Siam J. Disc. Math. 23 (2009), 369–371.
• [D1997] On the number of even and odd Latin squares of order [math]\displaystyle{ p + 1 }[/math], Arthur Drisko, Advances in Math. 128 (1997), 20–35.
• [EE2015] Furstenberg sets and Furstenberg schemes over finite fields, Jordan Ellenberg, Daniel Erman, Feb 2015.
• [GH2006] Rota's basis conjecture for paving matroids, J. Geelen, P. Humphries, SIAM J. Discrete Math. 20 (2006), no. 4, 1042–1045.
• [GW2007] On Rota's basis conjecture, Jim Geelen and Kerri Webb, SIAM J. Discrete Math. 21 (2007), 802–804.
• [G2010] The conjectures of Alon–Tarsi and Rota in dimension prime minus one, David G. Glynn, SIAM J. Discrete Math. 24 (2010), 394–399.
• [HKL2010] On disjoint common bases in two matroids, Nicholas J. A. Harvey, Tamás Király, and Lap Chi Lau, TR-2010-10. Published by the Egerváry Research Group, Pázmány P. sétány 1/C, H–1117, Budapest, Hungary.
• [HR1994] On the relations of various conjectures on Latin squares and straightening coefficients, Rosa Huang and Gian-Carlo Rota, Discrete Math. 128 (1994), 225–236.
• [K2012] On extensions of the Alon-Tarsi Latin square conjecture, Daniel Kotlar, Electronic J. Combin. 19 (2012), #P7.
• [O1997] A colorful determinantal identity, a conjecture of Rota, and Latin squares, Shmuel Onn, Amer. Math. Monthly 104 (1997), 156–159.
• [P2004] Reduction of jump systems, Vadim Ponomarenko, Houston J. Math. 30 (2004), 27–33.
• [SW2012] How not to prove the Alon–Tarsi conjecture, Douglas S. Stones and Ian M. Wanless, Nagoya Math J. 205 (2012), 1–24.
• [W1994] On Rota's problem about n bases in a rank n matroid, Marcel Wild, Advances in Math. 108 (1994), 336–345.
• [Z1997] The Cayley determinant of the determinant tensor and the Alon–Tarsi conjecture, Paolo Zappa, Advances Appl. Math. 19 (1997), 31–44. Warning: This paper contains a serious error and its results cannot be trusted.