×

Parity of transversals of Latin squares. (English) Zbl 1437.05033

Summary: We introduce a notion of parity for transversals, and use it to show that in Latin squares of order \(2 \pmod 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\mid j)\) 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(i\mid j)\), for some fixed Latin square \(L\). We show that \(t_{ab}\equiv t_{cd}\pmod 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} \pmod 2\). We conjecture that \(t_{ac} + t_{bc} + t_{ad} + t_{bd} \equiv 0 \pmod 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\pmod 4\). We also show that
\[\mathop{\text{per}}A(a \mid c)+\mathop{\text{per}}A(b \mid c)+\mathop{\text{per}}A(a \mid d)+\mathop{\text{per}}A(b \mid d) \equiv 0 \pmod 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\pmod 4\).

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares
05D15 Transversal (matching) theory
15A15 Determinants, permanents, traces, other special matrix functions
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aharoni, Ron; Loebl, Martin, The odd case of Rota’s bases conjecture, Adv. Math., 282, 427-442 (2015) · Zbl 1319.05024 · doi:10.1016/j.aim.2015.06.015
[2] Akbari, Saieed; Alipour, Alireza, Transversals and multicolored matchings, J. Comb. Des., 12, 5, 325-332 (2004) · Zbl 1053.05017 · doi:10.1002/jcd.20014
[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, 101, 4, 943-956 (2014) · Zbl 1306.62179 · doi:10.1093/biomet/asu036
[4] Alon, Noga; Tarsi, Michael, Colorings and orientations of graphs, Combinatorica, 12, 2, 125-134 (1992) · Zbl 0756.05049 · doi:10.1007/BF01204715
[5] Alpoge, Levent, Square-root cancellation for the signs of Latin squares, Combinatorica, 37, 2, 137-142 (2017) · Zbl 1399.05017 · doi:10.1007/s00493-015-3373-7
[6] Balasubramanian, Krishnaswami, On transversals in Latin squares, Linear Algebra Appl., 131, 125-129 (1990) · Zbl 0704.05007 · doi:10.1016/0024-3795(90)90378-P
[7] Barát, János; Nagy, Zoltán L., Transversals in generalized Latin squares, Ars Math. Contemp., 16, 1, 39-47 (2019) · Zbl 1416.05054 · doi:10.26493/1855-3974.1316.2d2
[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., 26, 2, 84-96 (2018) · Zbl 1391.05061 · doi:10.1002/jcd.21566
[9] Cavenagh, Nicholas J.; Wanless, Ian M., There are asymptotically the same number of Latin squares of each parity, Bull. Aust. Math. Soc., 94, 2, 187-194 (2016) · Zbl 1361.05021 · doi:10.1017/S0004972716000174
[10] Donovan, Diane M.; Grannell, Michael J.; Griggs, Terry S.; Lefevre, James G., On parity vectors of Latin squares, Graphs Comb., 26, 5, 673-684 (2010) · Zbl 1231.05034 · doi:10.1007/s00373-010-0942-9
[11] Francetić, Nevena; Herke, Sarada; Wanless, Ian M., Parity of sets of mutually orthogonal Latin squares, J. Comb. Theory, Ser. A, 155, 67-99 (2018) · Zbl 1377.05021 · doi:10.1016/j.jcta.2017.10.006
[12] Glynn, David G., The conjectures of Alon-Tarsi and Rota in dimension prime minus one, SIAM J. Discrete Math., 24, 2, 394-399 (2010) · Zbl 1227.05095 · doi:10.1137/090773751
[13] Glynn, David G.; Byatt, David, Graphs for orthogonal arrays and projective planes of even order, SIAM J. Discrete Math., 26, 3, 1076-1087 (2012) · Zbl 1283.51001 · doi:10.1137/100809155
[14] Janssen, Jeannette C. M., On even and odd Latin squares, J. Comb. Theory, Ser. A, 69, 1, 173-181 (1995) · Zbl 0819.05016 · doi:10.1016/0097-3165(95)90115-9
[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., 21, 2, 23 p. pp. (2014) · Zbl 1300.05254
[16] Keevash, Peter; Yepremyan, Liana, On the number of symbols that forces a transversal · Zbl 1466.05217 · doi:10.1017/S0963548319000282
[17] Kotlar, Daniel, Parity types, cycle structures and autotopisms of Latin squares, Electron. J. Comb., 19, 3, 17 p. pp. (2012) · Zbl 1253.05048
[18] McKay, Brendan D.; McLeod, Jeanette C.; Wanless, Ian M., The number of transversals in a Latin square, Des. Codes Cryptography, 40, 3, 269-284 (2006) · Zbl 1200.05039 · doi:10.1007/s10623-006-0012-8
[19] Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benjamin, Decompositions into spanning rainbow structures, Proc. Lond. Math. Soc. (3), 119, 4, 899-959 (2019) · Zbl 1429.05024 · doi:10.1112/plms.12245
[20] Newman, Morris, Combinatorial matrices with small determinants, Can. J. Math., 30, 4, 756-762 (1978) · Zbl 0388.15012 · doi:10.4153/CJM-1978-065-8
[21] Ryser, Herbert J., Combinatorial mathematics, 14, xiv+154 p. pp. (1963), Wiley · Zbl 0112.24806
[22] Ryser, Herbert J., Neuere Probleme der Kombinatorik, Vortrage über Kombinatorik Oberwolfach, 69-91 (1967)
[23] Stones, Douglas S.; Wanless, Ian M., How not to prove the Alon-Tarsi conjecture, Nagoya Math. J., 205, 1-24 (2012) · Zbl 1245.05011 · doi:10.1215/00277630-1543769
[24] Taranenko, Anna A., Permanents of multidimensional matrices: properties and applications, J. Appl. Ind. Math., 10, 4, 567-604 (2016) · Zbl 1374.05024 · doi:10.1134/S1990478916040141
[25] Wanless, Ian M., Cycle switches in Latin squares, Graphs Comb., 20, 4, 545-570 (2004) · Zbl 1053.05020 · doi:10.1007/s00373-004-0567-7
[26] Wanless, Ian M., Surveys in combinatorics 2011, 392, Transversals in Latin squares: a survey, 403-437 (2011), Cambridge Univ. Press: Cambridge Univ. Press, Cambridge · Zbl 1226.05067 · doi:10.1017/CBO9781139004114.010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.