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:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.103
Classification: 05B15,  15A15,  05C70
Keywords: parity, Latin square, transversal, permanent, Latin rectangle, perfect matching, permanental minor, bipartite graph
Best, Darcy 1; Wanless, Ian M. 1

1 School of Mathematics Monash University, Australia
@article{ALCO_2020__3_2_539_0,
     author = {Best, Darcy and Wanless, Ian M.},
     title = {Parity of transversals of {Latin} squares},
     journal = {Algebraic Combinatorics},
     pages = {539--557},
     publisher = {MathOA foundation},
     volume = {3},
     number = {2},
     year = {2020},
     doi = {10.5802/alco.103},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.103/}
}
TY  - JOUR
TI  - Parity of transversals of Latin squares
JO  - Algebraic Combinatorics
PY  - 2020
DA  - 2020///
SP  - 539
EP  - 557
VL  - 3
IS  - 2
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.103/
UR  - https://doi.org/10.5802/alco.103
DO  - 10.5802/alco.103
LA  - en
ID  - ALCO_2020__3_2_539_0
ER  - 
%0 Journal Article
%T Parity of transversals of Latin squares
%J Algebraic Combinatorics
%D 2020
%P 539-557
%V 3
%N 2
%I MathOA foundation
%U https://doi.org/10.5802/alco.103
%R 10.5802/alco.103
%G en
%F 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/articles/10.5802/alco.103/

[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, Paper no. Paper #2.49, 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, Paper no. Paper #10, 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 | Article | MR: 500230 | Zbl: 0388.15012

[21] Ryser, Herbert J. Combinatorial mathematics, Carus Math. Monogr., 14, Wiley, 1963, xiv+154 pages | MR: 0150048 | 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

Cited by Sources: