TOPICS
Search

Alon-Tarsi Conjecture


A Latin square is said to be odd if it contains an odd number of rows and columns that are odd permutations. Otherwise, it is said to be even.

Let the number of even Latin squares of order n be denoted els(n), and the number of odd Latin squares of order n be denoted ols(n). The following table summarizes the numbers of even and odd Latin squares for small n.

nels(n)ols(n)els(n)-ols(n)
SloaneA114628A114629A114630
1101
2202
3660
45760576
580640806400
6505958400306892800199065600
730739709952000307397099520000
855019078005712486400537569544533704704001262123552342016000

If n!=1 is odd, then switching two rows of a Latin square alters its sign, so els(n)=ols(n).

The Alon-Tarsi conjecture states that for even n, els(n)!=ols(n) (Drisko 1998).

Zappa (1997) generalized the conjecture to fixed diagonal Latin squares to encompass odd orders. Define a fixed diagonal Latin square as a Latin square for which all diagonal entries equal 1, and denote the numbers of fixed diagonal even and fixed diagonal odd Latin squares of order n by fdels(n) and fdols(n), respectively. For n=1, 2, ..., fdels(n) equals 1, 1, 0, 24, 384, ... (OEIS A114631), and fdols(n) equals 0, 0, 2, 0, 960, ... (OEIS A114632).

Further define the Alon-Tarsi constant by

 AT(n)=(fdels(n)-fdols(n))/((n-1)!)
(1)

(Drisko 1998). Then the values of AT(n) for n=1, 2, ... are 1, -1, 4, -24, 2304, 368640, 6210846720, ... (OEIS A065711; Drisko 1998).

The quantity AT(n) is related to the numbers of even and odd Latin squares by

 els(n)-ols(n)={n!(n-1)!AT(n)   for n even; 0   for n>1 odd; 1   for n=1
(2)

(Drisko 1998).

The extended Alon-Tarsi conjecture states that for every positive integer n, AT(n)!=0. This was proven for all n of the form p(2^r) for prime p by Drisko (1998).


See also

Latin Square

Portions of this entry contributed by Jonathan Vos Post (author's link)

Explore with Wolfram|Alpha

References

Alon, N. and Tarsi, M. "Coloring and Orientations of Graphs." Combinatorica 12, 125-143, 1992.Drisko, A. A. "On the Number of Even and Odd Latin Squares of Order p+1." Adv. Math. 128, 20-35, 1997.Drisko, A. A. "Proof of the Alon-Tarsi Conjecture for n=2^rp." Electronic J. Combinatorics 5, No. 1, R28, 1-5, 1998. http://www.combinatorics.org/Volume_5/Abstracts/v5i1r28.html.Huang, R. and Rota, G.-C. "On the Relations of Various Conjectures on Latin Squares and Straightening Coefficients." Disc. Math. 128, 237-245, 1994.Janssen, J. C. M. "On Even and Odd Latin Squares." J. Combin. Theory Ser. A 69, 173-181, 1995.Onn, S. "A Colorful Determinantal Identity, a Conjecture of Rota, and Latin Squares." Amer. Math. Monthly 104, 156-159, 1997.Sloane, N. J. A. Sequences A065711, A114628, A114629, A114630, A114631, and A114632 in "The On-Line Encyclopedia of Integer Sequences."Zappa, P. "The Cayley Determinant of the Determinant Tensor and the Alon-Tarsi Conjecture." Adv. Appl. Math. 19, 31-44, 1997.

Referenced on Wolfram|Alpha

Alon-Tarsi Conjecture

Cite this as:

Post, Jonathan Vos and Weisstein, Eric W. "Alon-Tarsi Conjecture." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Alon-TarsiConjecture.html

Subject classifications