# 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
License: CC-BY 4.0
@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
AU  - Best, Darcy
AU  - Wanless, Ian M.
TI  - Parity of transversals of Latin squares
JO  - Algebraic Combinatorics
PY  - 2020
SP  - 539
EP  - 557
VL  - 3
IS  - 2
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.103/
DO  - 10.5802/alco.103
LA  - en
ID  - ALCO_2020__3_2_539_0
ER  - 
%0 Journal Article
%A Best, Darcy
%A Wanless, Ian M.
%T Parity of transversals of Latin squares
%J Algebraic Combinatorics
%D 2020
%P 539-557
%V 3
%N 2
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/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 | DOI | MR | Zbl

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

 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 | DOI | MR | Zbl

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

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

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

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

 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 | DOI | MR | Zbl

 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 | DOI | MR | Zbl

 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 | DOI | MR | Zbl

 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 | DOI | MR | Zbl

 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 | DOI | MR | Zbl

 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 | DOI | MR | Zbl

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

 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 | Zbl

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

 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 | Zbl

 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 | DOI | MR | Zbl

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

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

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

 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 | DOI | MR | Zbl

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

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

 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 | DOI | MR | Zbl

Cited by Sources: