# The Alon-Tarsi basis conjecture

 Importance: Medium ✭✭
 Author(s): Alon, Noga Linial, Nathan Meshulam, Roy
 Subject: Combinatorics » Matrices
 Keywords: additive basis matrix
 Recomm. for undergrads: no
 Prize: none
 Posted by: mdevos on: March 8th, 2007
Conjecture   If are invertible matrices with entries in for a prime , then there is a submatrix of so that is an AT-base.

Definition: If is an matrix over a field of characteristic , then we say that is an Alon-Tarsi basis (or AT-basis) if the permanent of the matrix obtained by stacking copies of is nonzero.

It follows from the Alon-Tarsi polynomial technique that if is an AT-base then for every of size 2 and for every , there exists a vector so that (using the notation from A nowhere-zero point in a linear mapping, is (2,1)-choosable). It follows from this that every Alon-Tarsi base over is also an additive basis. Thus, the above conjecture, if true, would imply The additive basis conjecture. The following strengthening of this conjecture was suggested in [D]

Conjecture  (The strong Alon-Tarsi basis conjecture (DeVos))   If are invertible matrices with entries in a field of characteristic , then we may partition the columns of into an matrix and an matrix so that is an AT-base and is invertible.

In addition to implying the conjecture, above, if true, this conjecture would imply both The permanent conjecture and The choosability in conjecture.