Parity of transversals of Latin squares

DOI10.5802/ALCO.103MaRDI QIDQ1985367zbMATH OpenOpenAlexFDO

Authors Darcy Best, Ian M. Wanless

Publication date 7 April 2020

Published in Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1912.11230

zbMATH Keywords

bipartite graphLatin rectangleLatin squareparityperfect matchingpermanentpermanental minortransversal

Mathematics Subject Classification ID

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

Abstract: 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 $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(imidj)$ 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(imidj)$, for some fixed Latin square $L$. We show that $$ 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 $$ 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 $$. We also show that ${\displaystyle }${ m per}, A(a mid c)+{ m per}, A(b mid c)+{ m per}, A(a mid d)+{ m per}, A(b mid d) equiv 0 �mod 4${\displaystyle }$ for all $a,b,c,d$, when $A$ is an integer matrix of odd order with all row and columns sums equal to $$.

Recommendations

• On parity vectors of Latin squares
• Parity of sets of mutually orthogonal Latin squares
• On transversals in Latin squares
• Transversals in splitted Latin squares of even order
• scientific article; zbMATH DE number 4061257
• On the number of transversals in Latin squares
• Transversals in Latin Squares
• scientific article; zbMATH DE number 1161383
• Transversals in generalized Latin squares
• A generalization of transversals for Latin squares

Cites work

• Circular designs balanced for neighbours at distances one and two
• Colorings and orientations of graphs
• Combinatorial Matrices with Small Determinants
• Cycle switches in Latin squares
• Decompositions into spanning rainbow structures
• Graphs for orthogonal arrays and projective planes of even order
• How not to prove the Alon-Tarsi conjecture
• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• On even and odd latin squares
• On parity vectors of Latin squares
• On the number of symbols that forces a transversal
• On transversals in Latin squares
• Parity of sets of mutually orthogonal Latin squares
• Parity types, cycle structures and autotopisms of Latin squares
• Permanents of multidimensional matrices: properties and applications
• Square-root cancellation for the signs of Latin squares
• Switching in one-factorisations of complete graphs
• The conjectures of Alon-Tarsi and Rota in dimension prime minus one
• The number of transversals in a Latin square
• The odd case of Rota's bases conjecture
• There are asymptotically the same number of Latin squares of each parity
• Transversals and multicolored matchings
• Transversals in generalized Latin squares
• Transversals in Latin arrays with many distinct symbols
• Transversals in Latin squares: a survey

Cited in

(5)

• The Bruhat order on classes of isotopic Latin squares
• A short proof of the transversal theorem for Latin squares of even order
• scientific article; zbMATH DE number 3847389 (Why is no real title available?)
• Transversals in Latin Squares
• On transversals in Latin squares

This page was built for publication: Parity of transversals of Latin squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1985367)