Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Proof of the Alon-Tarsi Conjecture for n = 2r p. | Proof of the Alon-Tarsi Conjecture for n 2rp Arthur A. Drisko National Security Agency Fort George G. Meade MD 20755 Submitted April 10 1998 Accepted May 10 1998. Abstract The Alon-Tarsi conjecture states that for even n the number of even latin squares of order n differs from the number of odd latin squares of order n. Zappa 6 found a generalization of this conjecture which makes sense for odd orders. In this note we prove this extended Alon-Tarsi conjecture for prime orders p. By results of Drisko 2 and Zappa 6 this implies that both conjectures are true for any n of the form 2 p with p prime. 1 Introduction A latin square L of order n is an n X n matrix whose rows and columns are permutations of n symbols say 0 1 . n 1. Rows and columns will also be indexed by 0 1 . n 1. The sign sgn L of L is the product of the signs as permutations of the rows and columns of L. L is even respectively odd if sgn L is 1 respectively 1. A fixed diagonal latin square has all diagonal entries equal to 0. We denote the set of all latin squares of order n by LS n and the set of all fixed diagonal latin squares of order n by FDLS n . We denote the numbers of even odd fixed diagonal even and fixed diagonal odd latin squares of order n by els n ols n fdels n and fdols n respectively. If n 1 is odd then switching two rows of a latin square alters its sign so els n ols n . On the other hand Alon and Tarsi 1 conjectured Conjecture 1 Alon-Tarsi If n is even then els n ols n . Equivalently the sum of the signs of all L 2 LS n is nonzero. This conjecture is related to several other conjectures in combinatorics and linear algebra 3 5 . Zappa was able to generalize this conjecture to the odd case by defining the Alon-Tarsi constant AT n fdels n fdols n n 1 MR Subject Classification 1991 05B15 05E20 05A15 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 5 1998 R28 2 Since any latin square can be transformed into a fixed diagonal latin square by a permutation of rows .
