We introduce a notion of parity for transversals, and use it to show that in Latin squares of order , the number of transversals is a multiple of 4. We also demonstrate a number of relationships (mostly congruences modulo 4) involving , where is the number of diagonals of a given Latin square that contain exactly different symbols.
Let denote the matrix obtained by deleting row and column from a parent matrix . Define to be the number of transversals in , for some fixed Latin square . We show that for all and . Also, if has odd order then the number of transversals of equals mod 2. We conjecture that for all .
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 -regular bipartite graph on vertices is divisible by when is odd and . We also show that
for all , when is an integer matrix of odd order with all row and columns sums equal to .
Revised: 2019-07-09
Accepted: 2019-11-24
Published online: 2020-04-01
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 = {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/
[1] The odd case of Rota’s bases conjecture, Adv. Math., Volume 282 (2015), pp. 427-442 | Article | MR 3374531 | Zbl 1319.05024
[2] Transversals and multicolored matchings, J. Comb. Des., Volume 12 (2004) no. 5, pp. 325-332 | Article | MR 2079255 | Zbl 1053.05017
[3] 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] Colorings and orientations of graphs, Combinatorica, Volume 12 (1992) no. 2, pp. 125-134 | Article | MR 1179249 | Zbl 0756.05049
[5] 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] On transversals in Latin squares, Linear Algebra Appl., Volume 131 (1990), pp. 125-129 | Article | MR 1057068 | Zbl 0704.05007
[7] Transversals in generalized Latin squares, Ars Math. Contemp., Volume 16 (2019) no. 1, pp. 39-47 | Article | MR 3904714 | Zbl 1416.05054
[8] 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] 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] On parity vectors of Latin squares, Graphs Comb., Volume 26 (2010) no. 5, pp. 673-684 | Article | MR 2679938 | Zbl 1231.05034
[11] 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] 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] 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] 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] Switching in one-factorisations of complete graphs, Electron. J. Comb., Volume 21 (2014) no. 2, 23 pages | MR 3244815 | Zbl 1300.05254
[16] On the number of symbols that forces a transversal (to appear in Comb. Probab. Comput., 7 pages) | Article
[17] Parity types, cycle structures and autotopisms of Latin squares, Electron. J. Comb., Volume 19 (2012) no. 3, 17 pages | MR 2967215 | Zbl 1253.05048
[18] 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] 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] Combinatorial matrices with small determinants, Can. J. Math., Volume 30 (1978) no. 4, pp. 756-762 | MR 500230 | Zbl 0388.15012
[21] Combinatorial mathematics, Carus Math. Monogr., Volume 14, Wiley, 1963, xiv+154 pages | MR 150048 | Zbl 0112.24806
[22] Neuere Probleme der Kombinatorik, Vortrage über Kombinatorik Oberwolfach (1967), pp. 69-91
[23] How not to prove the Alon–Tarsi conjecture, Nagoya Math. J., Volume 205 (2012), pp. 1-24 | Article | MR 2891163 | Zbl 1245.05011
[24] 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] Cycle switches in Latin squares, Graphs Comb., Volume 20 (2004) no. 4, pp. 545-570 | Article | MR 2108400 | Zbl 1053.05020
[26] 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