×

The Cayley determinant of the determinant tensor and the Alon-Tarsi conjecture. (English) Zbl 0885.05035

Each row and column of a Latin square, \(L\), of order \(n\) can be thought of as a permutation of the elements in \(\{1,2,\dots,n\}\). \(L\) is even (odd) if the product of its row and column permutations is even (odd). A semi-normalized diagonal \(L\) is one for which the elements in the first column appear in natural order and only 1’s appear on the diagonal. Let \(\text{els}(n)\), respectively \(\text{ols}(n)\), denote the number of even, respectively odd, Latin squares of order \(n\), and affix a prefix of “snd” if we restrict to semi-normalized diagonal \(L\)’s. If \(n\) is odd, then \(\text{els}(n)-\text{ols}(n)= 0\). If \(n\) is even the Alon-Tarsi conjecture states that this difference is nonzero. The author defines the Alon-Tarsi constant \(\text{AT}(n)\) which equals \(\text{sndels}(n)- \text{sndols}(n)\), and notes it is not necessarily \(0\) for odd \(n\). Indeed, the author extends the Alon-Tarsi conjecture to \(\text{AT}(n)\neq 0\) for every positive integer \(n\). The author shows that \(\text{els}(n)- \text{ols}(n)\) is nonnegative, and proves the Alon-Tarsi conjecture for Latin squares of order \(c2^r\), where \(r\in\mathbb{Z}^+\) and either \(c\) is an even integer for which the Alon-Tarsi conjecture is true, or \(c\) is an odd integer such that the extended Alon-Tarsi conjecture is true for both \(c\) and \(c+1\). Coupled with recent work of Arthur A. Drisko [Adv. Math. 128, No. 1, 20-35 (1997; Zbl 0885.05034), above], this estabishes that the Alon-Tarsi conjecture is true for Latin squares of order \(2^r(p+1)\), where \(p\) is an odd prime.

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares
Full Text: DOI

Online Encyclopedia of Integer Sequences:

The Alon-Tarsi constants AT(n).

References:

[1] Alon, N.; Tarsi, M., Coloring and orientations of graphs, Combinatorica, 12, 125-143 (1992) · Zbl 0756.05049
[2] A. A. Drisko, On the number of even and odd Latin squares of order \(p\); A. A. Drisko, On the number of even and odd Latin squares of order \(p\) · Zbl 0885.05034
[3] Gherardelli, F., Osservazioni sugli iperdeterminanti, Istit. Lombardo Accad. Sci. Lett. Rend. A, 127, 107-113 (1993) · Zbl 0876.15005
[4] Huang, R.; Rota, G.-C., On the relations of various conjectures on Latin squares and straightening coefficients, Discrete Math., 128, 237-245 (1994)
[5] Marini, A.; Pirillo, G., Signs on Latin squares, Adv. in Appl. Math., 15, 490-505 (1994) · Zbl 0818.05017
[6] Zappa, P., Triplets of Latin squares, Boll. Un. Mat. Ital. A (7), 10, 63-69 (1996) · Zbl 0859.05023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.