Parity of transversals of Latin squares

Best, Darcy; Wanless, Ian M.

doi:10.5802/alco.103

Best, Darcy; Wanless, Ian M.

Algebraic Combinatorics, Volume 3 (2020) no. 2, pp. 539-557.

Abstract

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

Let $A (i ∣ j)$ denote the matrix obtained by deleting row $i$ and column $j$ from a parent matrix $A$ . Define $t_{i j}$ to be the number of transversals in $L (i ∣ j)$ , for some fixed Latin square $L$ . We show that $t_{a b} \equiv t_{c d} mod 2$ for all $a, b, c, d$ and $L$ . Also, if $L$ has odd order then the number of transversals of $L$ equals $t_{a b}$ mod 2. We conjecture that $t_{a c} + t_{b c} + t_{a d} + t_{b d} \equiv 0 mod 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 $2 n$ vertices is divisible by $4$ when $n$ is odd and $k \equiv 0 mod 4$ . We also show that

per A (a ∣ c) + per A (b ∣ c) + per A (a ∣ d) + per A (b ∣ d) \equiv 0 mod 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 mod 4$ .

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},
     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/}
}

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/

References

[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

ALGEBRAIC COMBINATORICS

About the Journal

Editorial Team

Author Guidelines

Submit a paper