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.

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.
• [C1995] 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.
• [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.

• [HKL2010] On disjoint common bases in two matroids, Nicholas J. A. Harvey, Tam´as Kir´aly, and Lap Chi Lau, TR-2010-10. Published by the Egerv´ary Research Group, P´azm´any P. s´et´any 1/C, H–1117, Budapest, Hungary.