Formulae for the Alon-Tarsi conjecture

Douglas Stuart Stones

Research output: Contribution to journalArticleResearchpeer-review

5 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-n(EVEN) and L-n(ODD) be, respectively, the number of Latin squares of order n with sign +1 and -1. The Alon-Tarsi conjecture asserts that L-n(EVEN) not equal L-n(ODD) when n is even. We prove that L-n(EVEN) - L-n(ODD) = (-1)(n(n-1)/2)Sigma(A is an element of Bn) (-1)(sigma 0(A)) det(A)(n), where B-n is the set of n x n (0, 1)-matrices and sigma(0)(A) is the number of 0 elements in A. We use this formula to give another proof of the Alon-Tarsi conjecture for n = p - 1 for odd prime p.
Original languageEnglish
Pages (from-to)65 - 70
Number of pages6
JournalSIAM Journal on Discrete Mathematics
Volume26
Issue number1
DOIs
Publication statusPublished - 2012

Cite this