# 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:
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/

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

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

Cited by Sources: