TOPICS

# 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 be denoted , and the number of odd Latin squares of order be denoted . The following table summarizes the numbers of even and odd Latin squares for small .

 Sloane A114628 A114629 A114630 1 1 0 1 2 2 0 2 3 6 6 0 4 576 0 576 5 80640 80640 0 6 505958400 306892800 199065600 7 30739709952000 30739709952000 0 8 55019078005712486400 53756954453370470400 1262123552342016000

If is odd, then switching two rows of a Latin square alters its sign, so .

The Alon-Tarsi conjecture states that for even , (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 by and , respectively. For , 2, ..., equals 1, 1, 0, 24, 384, ... (OEIS A114631), and equals 0, 0, 2, 0, 960, ... (OEIS A114632).

Further define the Alon-Tarsi constant by

 (1)

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

The quantity is related to the numbers of even and odd Latin squares by

 (2)

(Drisko 1998).

The extended Alon-Tarsi conjecture states that for every positive integer , . This was proven for all of the form for prime by Drisko (1998).

Latin Square

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

## Explore with Wolfram|Alpha

More things to try:

## 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 ." Adv. Math. 128, 20-35, 1997.Drisko, A. A. "Proof of the Alon-Tarsi Conjecture for ." 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