Rota's conjecture

From Polymath Wiki
Revision as of 12:03, 22 October 2017 by Chowt (talk | contribs) (→‎References)
Jump to navigationJump to search

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]1 and [math]\displaystyle{ B }[/math]2, there exists a bijection [math]\displaystyle{ f : B }[/math]1 → [math]\displaystyle{ B }[/math]2 such that for every subset [math]\displaystyle{ S ⊆ B }[/math]1, both [math]\displaystyle{ B }[/math]1 \ [math]\displaystyle{ S ∪ f(S) }[/math] and [math]\displaystyle{ B }[/math]2 \ [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 [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]2 modulo [math]\displaystyle{ p }[/math]3.

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

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.

Variants of the problem

Discussion

References

Other links

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Rota%27s_conjecture&oldid=9972"