TY - JOUR
T1 - How not to prove the Alon-Tarsi conjecture
AU - Stones, Douglas S.
AU - Wanless, Ian M.
PY - 2012
Y1 - 2012
N2 - The sign of a Latin square is -1 if it has an odd number of rows and columns that are odd permutations; otherwise, it is +1. Let L E n and L o n be, respectively, the number of Latin squares of order n with sign +1 and -1. The Alon-Tarsi conjecture asserts that L E n ≠ L o n when n is even. Drisko showed that L E p+1 ≡ L o p+1 (mod p 3) for prime p ≥ 3 and asked if similar congruences hold for orders of the form p k + 1, p + 3, or pq + 1. In this article we show that if t ≤ n, then L E n+ ≡ L o n+1 (mod t 3) only if t = n and n is an odd prime, thereby showing that Drisko's method cannot be extended to encompass any of the three suggested cases. We also extend exact computation to n ≤ 9, discuss asymptotics for L o/L E, and propose a generalization of the Alon-Tarsi conjecture.
AB - The sign of a Latin square is -1 if it has an odd number of rows and columns that are odd permutations; otherwise, it is +1. Let L E n and L o n be, respectively, the number of Latin squares of order n with sign +1 and -1. The Alon-Tarsi conjecture asserts that L E n ≠ L o n when n is even. Drisko showed that L E p+1 ≡ L o p+1 (mod p 3) for prime p ≥ 3 and asked if similar congruences hold for orders of the form p k + 1, p + 3, or pq + 1. In this article we show that if t ≤ n, then L E n+ ≡ L o n+1 (mod t 3) only if t = n and n is an odd prime, thereby showing that Drisko's method cannot be extended to encompass any of the three suggested cases. We also extend exact computation to n ≤ 9, discuss asymptotics for L o/L E, and propose a generalization of the Alon-Tarsi conjecture.
UR - http://www.scopus.com/inward/record.url?scp=84861056434&partnerID=8YFLogxK
U2 - 10.1215/00277630-1543769
DO - 10.1215/00277630-1543769
M3 - Article
SN - 0027-7630
VL - 205
SP - 1
EP - 24
JO - Nagoya Mathematical Journal
JF - Nagoya Mathematical Journal
ER -