The Alon-Tarsi basis conjecture

Definitions and mathematical statement

Fix a prime $p$ and an integer $n\ge1$. For an $m\times m$ matrix $D$ over a field, its permanent is \[ \operatorname{per}D=\sum_{\sigma\in S_m}\prod_{i=1}^mD_{i,\sigma(i)}, \] where $S_m$ denotes all permutations of $\{1,\ldots,m\}$; there are no alternating signs. Given an $n\times(p-1)n$ matrix $A$ over a field of characteristic $p$, stack $p-1$ identical copies vertically to form the square matrix $A^{\uparrow}$. Call $A$ an Alon--Tarsi basis when $\operatorname{per}(A^{\uparrow})\ne0$ in that field.

The basic conjecture says that, for every collection of invertible matrices $B_1,\ldots,B_p\in\mathbb F_p^{n\times n}$, the concatenated matrix $B=[B_1\ \cdots\ B_p]$ contains $(p-1)n$ columns forming an Alon--Tarsi basis. Columns are selected by position, so identical vectors occurring in different bases remain distinct available columns. Their order does not affect whether the permanent vanishes.

The source also proposes a stronger partition statement: over every field $K$ of characteristic $p$, the columns of any such concatenation of $p$ invertible matrices can be partitioned into an Alon--Tarsi basis $A$ and an invertible $n\times n$ matrix $C$. Thus the stronger assertion simultaneously requires a nonzero stacked permanent on the selected columns and linear independence of the omitted columns. All dimensions and all primes are quantified universally.

Short English statement

Select all but one basis-worth of columns from p bases so that the stacked permanent is nonzero; the stronger version also keeps the remaining columns independent.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3062 (OPG-152), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, The Alon-Tarsi basis conjecture. Original problem and discussion. http://www.openproblemgarden.org/op/the_alon_tarsi_basis_conjecture.
• S3 M. DeVos, Matrix Choosability, J. Combin. Theory A 90 (2000), 197--209. https://www.sfu.ca/~mdevos/papers/pliant.pdf.