Parity of transversals of Latin squares

Best, Darcy; Wanless, Ian M.

doi:10.5802/alco.103

Best, Darcy ¹; Wanless, Ian M.¹

¹ School of Mathematics Monash University, Australia

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: 10.5802/alco.103

Classification: 05B15, 15A15, 05C70
Keywords: parity, Latin square, transversal, permanent, Latin rectangle, perfect matching, permanental minor, bipartite graph

Author's affiliations:

Best, Darcy ¹; Wanless, Ian M. ¹

¹ School of Mathematics Monash University, Australia

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@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/

References
Cited by

[1] Aharoni, Ron; Loebl, Martin The odd case of Rota’s bases conjecture, Adv. Math., Volume 282 (2015), pp. 427-442 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

[14] 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

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

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

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

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

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

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

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

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

[24] 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

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

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

Cited by Sources: