Rota's conjecture

From Polymath Wiki
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 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

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

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

A generalization due to Jeff Kahn postulates [math]\displaystyle{ n }[/math]2 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]2 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]1, [math]\displaystyle{ I }[/math]2, …, [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

References

Other links

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