How not to prove the Alon-Tarsi conjecture

Douglas S. Stones*, Ian M. Wanless

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)1-24
Number of pages24
JournalNagoya Mathematical Journal
Volume205
DOIs
Publication statusPublished - 2012
Externally publishedYes

Fingerprint

Dive into the research topics of 'How not to prove the Alon-Tarsi conjecture'. Together they form a unique fingerprint.

Cite this