Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T06:27:14.698Z Has data issue: false hasContentIssue false
  • English
  • Français

How not to prove the Alon-Tarsi conjecture

Published online by Cambridge University Press:  11 January 2016

Douglas S. Stones  and
Ian M. Wanless
Douglas S. Stones
Affiliation:
School of Mathematical Sciences and Clayton School of Information Technology Monash University, Victoria 3800, [email protected]
Ian M. Wanless
Affiliation:
School of Mathematical Sciences Monash University, Victoria 3800, [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 LEn and Lon be, respectively, the number of Latin squares of order n with sign +1 and −1. The Alon-Tarsi conjecture asserts that LEn ≠ Lon when n is even. Drisko showed that LEp+1 ≢ Lop+1 (mod p3) for prime p ≥ 3 and asked if similar congruences hold for orders of the form pk + 1, p + 3, or pq + 1. In this article we show that if t ≤ n, then LEn+1 ≢ L0n+1 (mod t3) 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 Lo/LE, and propose a generalization of the Alon-Tarsi conjecture.

Keywords

05B1511B50
Type
Research Article
Information
Nagoya Mathematical Journal , Volume 205 , March 2012 , pp. 1 - 24
Copyright
Copyright © Editorial Board of Nagoya Mathematical Journal 2012

References

[1] Alon, N. and Tarsi, M., Colorings and orientations of graphs, Combinatorica 12 (1992), 125–134.CrossRefGoogle Scholar
[2] Cavenagh, N. J., Greenhill, C., and Wanless, I. M., The cycle structure of two rows in a random Latin square, Random Structures Algorithms 33 (2008), 286–309.CrossRefGoogle Scholar
[3] Chow, T. Y., On the Dinitz conjecture and related conjectures, Discrete Math. 145 (1995), 73–82.CrossRefGoogle Scholar
[4] Drisko, A. A., On the number of even and odd Latin squares of order p + 1, Adv. Math. 128 (1997), 20–35.CrossRefGoogle Scholar
[5] Drisko, A. A., Proof of the Alon-Tarsi conjecture for n = 2rp, Electron. J. Combin. 5 (1998), no. R28.CrossRefGoogle Scholar
[6] Erdős, P., Rubin, A. L., and Taylor, H., “Choosability in graphs” in Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Arcata, Calif., 1979), Congr. Numer. 26, Utilitas Mathematica, Winnipeg, 1980, 125–157.Google Scholar
[7] Galvin, F., The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B 63 (1995), 153–158.CrossRefGoogle Scholar
[8] Glynn, D. G., The conjectures of Alon-Tarsi and Rota in dimension prime minus one, SIAM J. Discrete Math. 24 (2010), 394–399.CrossRefGoogle Scholar
[9] Habsieger, L. and Janssen, J. C. M., The difference in even and odd Latin rectangles for small cases, Ann. Sci. Math. Québec 19 (1995), 69–77.Google Scholar
[10] Häggkvist, R., “Towards a solution of the Dinitz problem?” in Graph Theory and Combinatorics (Cambridge 1988), Discrete Math. 75, Elsevier, Amsterdam, 1989, 247–251.Google Scholar
[11] Häggkvist, R. and Janssen, J. C. M., All-even Latin squares, Discrete Math. 157 (1996), 199–206.CrossRefGoogle Scholar
[12] Huang, R. and Rota, G.-C., On the relations of various conjectures on Latin squares and straightening coefficients, Discrete Math. 128 (1994), 225–236.CrossRefGoogle Scholar
[13] Janssen, J. C. M., The Dinitz problem solved for rectangles, Bull. Amer. Math. Soc. (N.S.) 29 (1993), 243–249.CrossRefGoogle Scholar
[14] Janssen, J. C. M., On even and odd Latin squares, J. Combin. Theory Ser. A 69 (1995), 173–181.CrossRefGoogle Scholar
[15] Marini, A. and Pirillo, G., Signs on Latin squares, Adv. in Appl. Math. 15 (1994), 490–505.CrossRefGoogle Scholar
[16] Marini, A. and Pirillo, G., Signs on group Latin squares, Adv. in Appl. Math. 17 (1996), 117–121.CrossRefGoogle Scholar
[17] McKay, B. D. and Wanless, I. M., On the number of Latin squares, Ann. Comb. 9 (2005), 335–344.CrossRefGoogle Scholar
[18] Onn, S., A colorful determinantal identity, a conjecture of Rota, and Latin squares, Amer. Math. Monthly 104 (1997), 156–159.CrossRefGoogle Scholar
[19] Sade, A., Autotopies des quasigroupes et des systèmes associatifs, Arch. Math. (Brno) 4 (1968), 1–23.Google Scholar
[20] Slivnik, T., Short proof of Galvin’s theorem on the list-chromatic index of a bipartite multigraph, Combin. Probab. Comput. 5 (1996), 91–94.CrossRefGoogle Scholar
[21] Stones, D. S., The many formulae for the number of Latin rectangles, Electron. J. Combin. 17 (2010), no. A1.CrossRefGoogle Scholar
[22] Stones, D. S., Formulae for the Alon-Tarsi conjecture, preprint, to appear in SIAM J. Discrete Math. Google Scholar
[23] Stones, D. S. and Wanless, I. M., Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A 117 (2010), 204–215.CrossRefGoogle Scholar
[24] Stones, D. S. and Wanless, I. M., A congruence connecting Latin rectangles and partial orthomorphisms, preprint, to appear in Ann. Comb. Google Scholar
[25] Wanless, I. M., Cycle switches in Latin squares, Graphs Combin. 20 (2004), 545–570.CrossRefGoogle Scholar
[26] Zappa, P., Triplets of Latin squares, Boll. Un. Mat. Ital. A (7) 10 (1996), 63–69.Google Scholar
[27] Zappa, P., The Cayley determinant of the determinant tensor and the Alon-Tarsi conjecture, Adv. in Appl. Math. 19 (1997), 31–44.CrossRefGoogle Scholar
[28] Zeilberger, D., The method of undetermined generalization and specialization, Amer. Math. Monthly 103 (1996), 233–239.Google Scholar
[29] Zeng, J., The generating function for the difference in even and odd three-line Latin rectangles, Ann. Sci. Math. Québec 20 (1996), 105–108.Google Scholar