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 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] ∈ ℐ.

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.