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 (hereafter abbreviated to RBC) 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 paving matroid is a matroid in which every circuit has size [math]\displaystyle{ n }[/math] or [math]\displaystyle{ n+1 }[/math], where [math]\displaystyle{ n }[/math] is the rank.

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. A Latin square is reduced if its first row and its first column are both identity permutations.

Partial results

What follows is not a complete list of partial results, but some attempt has been made to list all major partial results that can be succinctly stated.

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 [AT1992] 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 [HR1994]. 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 [D1997]. 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 [G2010]. 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]. Note that there are known upper bounds for the value of AT([math]\displaystyle{ n }[/math]) [A2015, CW2016] but this does not seem to imply anything directly about RBC or the Alon–Tarsi Conjecture.

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

Theorem 4 [W1994]. RBC is true for strongly base-orderable matroids.

Theorem 5 [GH2006]. RBC is true for paving matroids.

Theorem 6 [Chan1995, C2012]. RBC is true for matroids of rank at most 4. (Note: C2012 is unpublished as of this writing.)

It is convenient to think of RBC as talking about a matroid [math]\displaystyle{ M }[/math] on a ground set [math]\displaystyle{ E }[/math] with exactly [math]\displaystyle{ n }[/math]² elements that is partitioned into [math]\displaystyle{ n }[/math] disjoint bases [math]\displaystyle{ B }[/math]_{[math]\displaystyle{ i }[/math]}; if some of the original bases intersect, then the repeated elements may be replaced with parallel "copies" of the same element. With this understanding, a partial transversal is a subset of [math]\displaystyle{ E }[/math] that intersects each [math]\displaystyle{ B }[/math]_{[math]\displaystyle{ i }[/math]} at most once, and a transversal is a partial transversal with [math]\displaystyle{ n }[/math] elements.

If one cannot prove that there are [math]\displaystyle{ n }[/math] disjoint transversals that are all bases of [math]\displaystyle{ M }[/math], one may still be able to guarantee at least [math]\displaystyle{ f(n) }[/math] disjoint transversals that are bases, for some [math]\displaystyle{ f(n) < n }[/math].

Theorem 7 [GW2007, DG2017]. Under the hypotheses of RBC, there exist at least ⌊ [math]\displaystyle{ n }[/math]/(6⌈log [math]\displaystyle{ n }[/math]⌉)⌋ disjoint transversals that are all bases. (Note: GW2007 established a lower bound of [math]\displaystyle{ O(√n) }[/math] which was later improved by DG2017, but DG2017 is unpublished as of this writing.)

Theorem 8 [W1994]. For a graphic matroid coming from a graph with maximum degree [math]\displaystyle{ d < n/3 }[/math], it is possible to construct [math]\displaystyle{ ⌈ (n+3d)/2d⌉ - 1 }[/math] disjoint transversals that are all bases.

We can form another matroid [math]\displaystyle{ N }[/math] on [math]\displaystyle{ E }[/math] by letting the independent sets of [math]\displaystyle{ N }[/math] be the partial transversals of [math]\displaystyle{ M }[/math]. Then RBC can be restated as saying that the minimum number [math]\displaystyle{ β }[/math] of disjoint common independent sets (i.e., independent in both [math]\displaystyle{ M }[/math] and [math]\displaystyle{ N }[/math]) into which [math]\displaystyle{ E }[/math] may be partitioned is [math]\displaystyle{ n }[/math].

Theorem 9 [AB2006, Polymath12]. [math]\displaystyle{ β ≤ 2n-2 }[/math]. (Note: AB2006 proved that [math]\displaystyle{ β ≤ 2n }[/math] and this was improved to [math]\displaystyle{ β ≤ 2n-2 }[/math] by Polymath12.)

Theorem 10 [P2004]. There is a grid of vectors such that for all [math]\displaystyle{ i }[/math], the first [math]\displaystyle{ i }[/math] columns of the grid comprise a disjoint union of [math]\displaystyle{ i }[/math] bases.

Variants of the problem

Again this list is not meant to be an exhaustive list of variants.

RBC generalizes immediately to arbitrary matroids and no matroid counterexample is known.

A generalization due to Jeff Kahn postulates [math]\displaystyle{ n }[/math]² bases [math]\displaystyle{ B }[/math]_{[math]\displaystyle{ ij }[/math]} of a vector space of dimension [math]\displaystyle{ n }[/math], and asks if there exists a choice of [math]\displaystyle{ n }[/math]² elements [math]\displaystyle{ v }[/math]_{[math]\displaystyle{ ij }[/math]}, one from each [math]\displaystyle{ B }[/math]_{[math]\displaystyle{ ij }[/math]}, such that the rows and columns are all bases (i.e., that {[math]\displaystyle{ v }[/math]_{[math]\displaystyle{ ij }[/math]}} is a basis for any fixed [math]\displaystyle{ i }[/math] and for any fixed [math]\displaystyle{ j }[/math]).

RBC may be thought of as a conjecture about square shapes. [CFGV2003] extend RBC to shapes of what that they call wide partitions. A partition [math]\displaystyle{ λ }[/math] is wide if [math]\displaystyle{ μ ≥ μ' }[/math] for every partition [math]\displaystyle{ μ }[/math] whose parts are a submultiset of the multiset of parts of [math]\displaystyle{ λ }[/math]. Here [math]\displaystyle{ ≥ }[/math] denotes dominance (a.k.a. majorization) order and [math]\displaystyle{ μ' }[/math] denotes the conjugate of [math]\displaystyle{ μ }[/math].

The online version of RBC posits that the bases are revealed one at a time, and the ordering of the elements of each basis must be chosen without knowing what the future bases are. [BD2015] prove that if the characteristic if the field does not divide AT([math]\displaystyle{ n }[/math]), then the online version is true for that value of [math]\displaystyle{ n }[/math]. On the other hand, if [math]\displaystyle{ n }[/math] is odd and the field contains an [math]\displaystyle{ m }[/math]th root of unity for all odd [math]\displaystyle{ m < n }[/math], then the online version of RBC is false. One positive outcome of Polymath12 was to improve our understanding of the online version of RBC.

[KL2015] give several equivalent formulations of the Alon–Tarsi Conjecture in terms of certain integrals over the special unitary group. [G2016] gives an equivalent formulation of the Alon–Tarsi Conjecture in terms of spherical functions.

Various attempts have been made to formulate an Alon–Tarsi Conjecture for odd [math]\displaystyle{ n }[/math]. For example, it is conjectured by [SW2012] that the number of reduced even Latin squares is not equal to the number of reduced odd Latin squares; [AL2015] prove that this is equivalent to the original Alon–Tarsi conjecture. [Z1997] has a related conjecture where "reduced" is replaced by "the first row is the identity permutation and the diagonal is all 1's."

[C2009] proposes the following conjecture. For [math]\displaystyle{ k ≤ n }[/math], let [math]\displaystyle{ M }[/math] be a matroid of rank [math]\displaystyle{ k }[/math] on [math]\displaystyle{ kn }[/math] elements that is a disjoint union of [math]\displaystyle{ k }[/math] bases. Let [math]\displaystyle{ I }[/math]₁, [math]\displaystyle{ I }[/math]₂, …, [math]\displaystyle{ I }[/math]_{[math]\displaystyle{ n }[/math]} be disjoint independent sets of [math]\displaystyle{ M }[/math], with 0 ≤ |[math]\displaystyle{ I }[/math]_{[math]\displaystyle{ i }[/math]}| ≤ [math]\displaystyle{ k }[/math] for all [math]\displaystyle{ i }[/math]. Then there exists an [math]\displaystyle{ n }[/math] × [math]\displaystyle{ k }[/math] grid [math]\displaystyle{ G }[/math] containing each element of [math]\displaystyle{ M }[/math] exactly once, such that for every [math]\displaystyle{ i }[/math], the elements of [math]\displaystyle{ I }[/math]_{[math]\displaystyle{ i }[/math]} appear in the [math]\displaystyle{ i }[/math]th row of [math]\displaystyle{ G }[/math] and such that every column of [math]\displaystyle{ G }[/math] is a basis of [math]\displaystyle{ M }[/math]. It is shown that for any fixed [math]\displaystyle{ k }[/math], this conjecture would imply RBC, but unfortunately [HKL2010] show that it is false for [math]\displaystyle{ k ≤ n/3 }[/math]. These counterexamples are useful for disproving various other overly strong generalizations of RBC.

Discussion

• Proposal on MathOverflow (Feb 15, 2016)
• Rota’s Basis Conjecture: Polymath 12? (Feb 23, 2017)
• Rota's Basis Conjecture: Polymath 12 (March 6, 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.
• [AL2015] The odd case of Rota's bases conjecture, Ron Aharoni and Martin Loebl, Advances Math. 282 (2015), 427–442.
• [AT1992] Colorings and orientations of graphs, N. Alon and M. Tarsi, Combinatorica 12 (1992), 125–134.
• [A2015] Square-root cancellation for the signs of Latin squares, Levent Alpoge, Combinatorica 6pp. DOI: 10.1007/s00493-015-3373-7
• [BGZ2012] Approaches to Rota's basis conjecture, Stephanie Bittner, Xuyi Guo and Adam Zweber, unpublished manuscript.
• [BDGOZ2013] Integer invariants of an incidence matrix related to Rota's basis conjecture, Stephanie Bittner, Joshua Ducey, Xuyi Guo, Minah Oh and Adam Zweber, arXiv:1304.2005.
• [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.
• [C2012] Computational proof of Rota's basis conjecture for matroids of rank 4, Michael Sze-yu Cheung, unpublished manuscript.
• [Chow1995] On the Dinitz conjecture and related conjectures, Timothy Chow, Disc. Math. 145 (1995), 73–82.
• [CFGV2003] Wide partitions, Latin tableaux, and Rota’s basis conjecture, Timothy Chow, C. Kenneth Fan, Michel X. Goemans and Jan Vondrak, Advances Appl. Math. 31 (2003), 334–358.
• [C2009] Reduction of Rota's basis conjecture to a conjecture on three bases, Timothy Chow, Siam J. Disc. Math. 23 (2009), 369–371.
• [CW2016] There are asymptotically the same number of Latin squares of each parity, Nicholas J. Cavenagh and Ian M. Wanless, Bull. Aust. Math. Soc. 94 (2016), 187–194.
• [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.
• [D1998] Proof of the Alon–Tarsi conjecture for [math]\displaystyle{ n }[/math] = 2^{[math]\displaystyle{ r }[/math]}[math]\displaystyle{ p }[/math], Arthur Drisko, Electronic J. Combin. 5 (1998), #R28. Warning: This paper builds on [Z1997], which is wrong.
• [DG2017] Improved bounds for Rota's basis conjecture, Sally Dong and Jim Geelen, arXiv:1709.00075.
• [EE2015] Furstenberg sets and Furstenberg schemes over finite fields, Jordan Ellenberg, Daniel Erman, Feb 2015.
• [F2013] A problem attributed to Rado from Mirsky’s 1971 monograph Transversal Theory and a conjecture from the 1982 Proceedings of the American Mathematical Society, Jonathan Farley, Math. Pannon. 24 (2013), 3–14.
• [G1995] The list chromatic index of a bipartite multigraph, Fred Galvin, J. Combin. Theory Ser. A 63 (1995), 153–158.
• [G2016] On the conjecture of Alon–Tarsi Carlos Gamas, Gulf J. Math 4 (2016), 108–116.
• [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.
• [J1993] The Dinitz problem solved for rectangles, Jeannette C. M. Janssen, Bull. Amer. Math. Soc. 29 (1993), 243–249.
• [J1995] On even and odd Latin squares, Jeannette C. M. Janssen, J. Combin. Theory Ser. A 69 (1995), 173–181.
• [KP2012] Partitions of nonzero elements of a finite field into pairs R. N. Karasev and F. V. Petrov, Israel J. Math. 192 (2012), 143–156.
• [K2012] On extensions of the Alon-Tarsi Latin square conjecture, Daniel Kotlar, Electronic J. Combin. 19 (2012), #P7.
• [KL2015] Connections between conjectures of Alon–Tarsi, Hadamard–Howe, and integrals over the special unitary group, Shrawan Kumar and J. M. Landsberg, Discrete Math. 338 (2015), 1232–1238.
• [O1997] A colorful determinantal identity, a conjecture of Rota, and Latin squares, Shmuel Onn, Amer. Math. Monthly 104 (1997), 156–159.
• [P2017] Tverberg type theorems for matroids, Pavel Paták, arXiv:1702:08170.
• [P2004] Reduction of jump systems, Vadim Ponomarenko, Houston J. Math. 30 (2004), 27–33.
• [S2012] Formulae for the Alon–Tarsi Conjecture, Douglas S. Stones, SIAM J. Discrete Math. 26 (2012), 65–70.
• [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.

Other links

• All matroids on nine elements, Dillon Mayhew and Gordon F. Royle.
• Alon–Tarsi conjecture for odd [math]\displaystyle{ n }[/math], Abdelmalek Abdesselam.