Math Conjectures

Alon–Tarsi Latin Square Conjecture

OPENMajorConjectureProposed 1990 · Standard version

Canonical statement

Let nn be even. Regard every row and every column of a Latin square LL of order nn as a permutation of its symbol set, and define
sgn⁡(L)=∏i=1nsgn⁡(rowi)∏j=1nsgn⁡(columnj). \operatorname{sgn}(L)= \prod_{i=1}^{n}\operatorname{sgn}(\text{row}_i) \prod_{j=1}^{n}\operatorname{sgn}(\text{column}_j).
The number of Latin squares of order nn with sign +1+1 is different from the number with sign −1-1.
View source LaTeX
Let \(n\) be even. Regard every row and every column of a
Latin square \(L\) of order \(n\) as a permutation of its symbol set, and
define
\[
  \operatorname{sgn}(L)=
  \prod_{i=1}^{n}\operatorname{sgn}(\text{row}_i)
  \prod_{j=1}^{n}\operatorname{sgn}(\text{column}_j).
\]
The number of Latin squares of order \(n\) with sign \(+1\) is different
from the number with sign \(-1\).
COMB-011:[AlonTarsi1992][Drisko1998]
CombinatoricsAlgebra and representation theory

Notes

Assign to a Latin square LL of even order nn the sign sgn⁡(L)\operatorname{sgn}(L), the product of the signs of its 2n2n row and column permutations. The Alon–Tarsi conjecture asserts that the number of Latin squares of order nn with sign +1+1 differs from the number with sign −1-1. It was posed by Alon and Tarsi around 1990 in connection with their polynomial method for colorings and orientations of graphs [AlonTarsi1992].

The restriction to even nn is essential, since for odd orders the two counts coincide and the difference vanishes identically. Much of the conjecture's interest lies in its consequences: by the Alon–Tarsi machinery, nonvanishing of the signed count yields strong list-coloring conclusions [AlonTarsi1992]. On the positive side, Drisko established the conjecture for orders of the form p+1p+1 with pp an odd prime [Drisko1998], and it is now known for several infinite families of even orders.

No argument covers all even nn, however, and the conjecture, together with the list-coloring consequences that would flow from it, remains open.

References (2)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.