# ALGEBRAIC COMBINATORICS

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 $2\phantom{\rule{0.277778em}{0ex}}mod\phantom{\rule{0.277778em}{0ex}}4$, the number of transversals is a multiple of 4. We also demonstrate a number of relationships (mostly congruences modulo 4) involving ${E}_{1},\cdots ,{E}_{n}$, where ${E}_{i}$ is the number of diagonals of a given Latin square that contain exactly $i$ different symbols.

Let $A\left(i\mid j\right)$ 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\left(i\mid j\right)$, for some fixed Latin square $L$. We show that ${t}_{ab}\equiv {t}_{cd}\phantom{\rule{0.277778em}{0ex}}mod\phantom{\rule{0.277778em}{0ex}}2$ 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}\equiv 0\phantom{\rule{0.277778em}{0ex}}mod\phantom{\rule{0.277778em}{0ex}}4$ 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 $k\equiv 0\phantom{\rule{0.277778em}{0ex}}mod\phantom{\rule{0.277778em}{0ex}}4$. We also show that

$\mathrm{per}A\left(a\mid c\right)+\mathrm{per}A\left(b\mid c\right)+\mathrm{per}A\left(a\mid d\right)+\mathrm{per}A\left(b\mid d\right)\equiv 0\phantom{\rule{0.277778em}{0ex}}mod\phantom{\rule{0.277778em}{0ex}}4$

for all $a,b,c,d$, when $A$ is an integer matrix of odd order with all row and columns sums equal to $k\equiv 2\phantom{\rule{0.277778em}{0ex}}mod\phantom{\rule{0.277778em}{0ex}}4$.

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/

 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

 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

 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

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

 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

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

 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

 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

 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

 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

 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

 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

 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

 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

 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

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

 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

 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

 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

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

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

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

 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

 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

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

 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