Parity of transversals of Latin squares
Algebraic Combinatorics, Volume 3 (2020) no. 2, pp. 539-557.

We introduce a notion of parity for transversals, and use it to show that in Latin squares of order 2mod4, the number of transversals is a multiple of 4. We also demonstrate a number of relationships (mostly congruences modulo 4) involving E 1 ,,E n , where E i is the number of diagonals of a given Latin square that contain exactly i different symbols.

Let A(ij) denote the matrix obtained by deleting row i and column j from a parent matrix A. Define t ij to be the number of transversals in L(ij), for some fixed Latin square L. We show that t ab t cd mod2 for all a,b,c,d and L. Also, if L has odd order then the number of transversals of L equals t ab mod 2. We conjecture that t ac +t bc +t ad +t bd 0mod4 for all a,b,c,d.

In the course of our investigations we prove several results that could be of interest in other contexts. For example, we show that the number of perfect matchings in a k-regular bipartite graph on 2n vertices is divisible by 4 when n is odd and k0mod4. We also show that

perA(ac)+perA(bc)+perA(ad)+perA(bd)0mod4

for all a,b,c,d, when A is an integer matrix of odd order with all row and columns sums equal to k2mod4.

Received: 2019-02-23
Revised: 2019-07-10
Accepted: 2019-11-25
Published online: 2020-04-01
DOI: https://doi.org/10.5802/alco.103
Classification: 05B15,  15A15,  05C70
Keywords: parity, Latin square, transversal, permanent, Latin rectangle, perfect matching, permanental minor, bipartite graph
@article{ALCO_2020__3_2_539_0,
     author = {Best, Darcy and Wanless, Ian M.},
     title = {Parity of transversals of Latin squares},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {3},
     number = {2},
     year = {2020},
     pages = {539-557},
     doi = {10.5802/alco.103},
     language = {en},
     url = {alco.centre-mersenne.org/item/ALCO_2020__3_2_539_0/}
}
Best, Darcy; Wanless, Ian M. Parity of transversals of Latin squares. Algebraic Combinatorics, Volume 3 (2020) no. 2, pp. 539-557. doi : 10.5802/alco.103. https://alco.centre-mersenne.org/item/ALCO_2020__3_2_539_0/

[1] Aharoni, Ron; Loebl, Martin The odd case of Rota’s bases conjecture, Adv. Math., Volume 282 (2015), pp. 427-442 | Article | MR 3374531 | Zbl 1319.05024

[2] Akbari, Saieed; Alipour, Alireza Transversals and multicolored matchings, J. Comb. Des., Volume 12 (2004) no. 5, pp. 325-332 | Article | MR 2079255 | Zbl 1053.05017

[3] Aldred, Robert E. L.; Bailey, Rosemary A.; McKay, Brendan D.; Wanless, Ian M. Circular designs balanced for neighbours at distances one and two, Biometrika, Volume 101 (2014) no. 4, pp. 943-956 | Article | MR 3286927 | Zbl 1306.62179

[4] Alon, Noga; Tarsi, Michael Colorings and orientations of graphs, Combinatorica, Volume 12 (1992) no. 2, pp. 125-134 | Article | MR 1179249 | Zbl 0756.05049

[5] Alpoge, Levent Square-root cancellation for the signs of Latin squares, Combinatorica, Volume 37 (2017) no. 2, pp. 137-142 | Article | MR 3638338 | Zbl 1399.05017

[6] Balasubramanian, Krishnaswami On transversals in Latin squares, Linear Algebra Appl., Volume 131 (1990), pp. 125-129 | Article | MR 1057068 | Zbl 0704.05007

[7] Barát, János; Nagy, Zoltán L. Transversals in generalized Latin squares, Ars Math. Contemp., Volume 16 (2019) no. 1, pp. 39-47 | Article | MR 3904714 | Zbl 1416.05054

[8] Best, Darcy; Hendrey, Kevin; Wanless, Ian M.; Wilson, Tim E.; Wood, David R. Transversals in Latin arrays with many distinct symbols, J. Comb. Des., Volume 26 (2018) no. 2, pp. 84-96 | Article | MR 3745158 | Zbl 1391.05061

[9] Cavenagh, Nicholas J.; Wanless, Ian M. There are asymptotically the same number of Latin squares of each parity, Bull. Aust. Math. Soc., Volume 94 (2016) no. 2, pp. 187-194 | Article | MR 3568910 | Zbl 1361.05021

[10] Donovan, Diane M.; Grannell, Michael J.; Griggs, Terry S.; Lefevre, James G. On parity vectors of Latin squares, Graphs Comb., Volume 26 (2010) no. 5, pp. 673-684 | Article | MR 2679938 | Zbl 1231.05034

[11] Francetić, Nevena; Herke, Sarada; Wanless, Ian M. Parity of sets of mutually orthogonal Latin squares, J. Comb. Theory, Ser. A, Volume 155 (2018), pp. 67-99 | Article | MR 3741421 | Zbl 1377.05021

[12] Glynn, David G. The conjectures of Alon-Tarsi and Rota in dimension prime minus one, SIAM J. Discrete Math., Volume 24 (2010) no. 2, pp. 394-399 | Article | MR 2646093 | Zbl 1227.05095

[13] Glynn, David G.; Byatt, David Graphs for orthogonal arrays and projective planes of even order, SIAM J. Discrete Math., Volume 26 (2012) no. 3, pp. 1076-1087 | Article | MR 3022125 | Zbl 1283.51001

[14] Janssen, Jeannette C. M. On even and odd Latin squares, J. Comb. Theory, Ser. A, Volume 69 (1995) no. 1, pp. 173-181 | Article | MR 1309160 | Zbl 0819.05016

[15] Kaski, Petteri; Medeiros, André de Souza; Östergård, Patric R. J.; Wanless, Ian M. Switching in one-factorisations of complete graphs, Electron. J. Comb., Volume 21 (2014) no. 2, 23 pages | MR 3244815 | Zbl 1300.05254

[16] Keevash, Peter; Yepremyan, Liana On the number of symbols that forces a transversal (to appear in Comb. Probab. Comput., 7 pages) | Article

[17] Kotlar, Daniel Parity types, cycle structures and autotopisms of Latin squares, Electron. J. Comb., Volume 19 (2012) no. 3, 17 pages | MR 2967215 | Zbl 1253.05048

[18] McKay, Brendan D; McLeod, Jeanette C.; Wanless, Ian M. The number of transversals in a Latin square, Des. Codes Cryptography, Volume 40 (2006) no. 3, pp. 269-284 | Article | MR 2251320 | Zbl 1200.05039

[19] Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benjamin Decompositions into spanning rainbow structures, Proc. Lond. Math. Soc. (3), Volume 119 (2019) no. 4, pp. 899-959 | Article | MR 3964824 | Zbl 1429.05024

[20] Newman, Morris Combinatorial matrices with small determinants, Can. J. Math., Volume 30 (1978) no. 4, pp. 756-762 | MR 500230 | Zbl 0388.15012

[21] Ryser, Herbert J. Combinatorial mathematics, Carus Math. Monogr., Volume 14, Wiley, 1963, xiv+154 pages | MR 150048 | Zbl 0112.24806

[22] Ryser, Herbert J. Neuere Probleme der Kombinatorik, Vortrage über Kombinatorik Oberwolfach (1967), pp. 69-91

[23] Stones, Douglas S.; Wanless, Ian M. How not to prove the Alon–Tarsi conjecture, Nagoya Math. J., Volume 205 (2012), pp. 1-24 | Article | MR 2891163 | Zbl 1245.05011

[24] Taranenko, Anna A. Permanents of multidimensional matrices: properties and applications, J. Appl. Ind. Math., Volume 10 (2016) no. 4, pp. 567-604 | Article | MR 3581885 | Zbl 1374.05024

[25] Wanless, Ian M. Cycle switches in Latin squares, Graphs Comb., Volume 20 (2004) no. 4, pp. 545-570 | Article | MR 2108400 | Zbl 1053.05020

[26] Wanless, Ian M. Transversals in Latin squares: a survey, Surveys in combinatorics 2011 (London Math. Soc. Lecture Note Ser.) Volume 392, Cambridge Univ. Press, Cambridge, 2011, pp. 403-437 | Article | MR 2866738 | Zbl 1226.05067