Parity of transversals of Latin squares

DOI10.5802/ALCO.103zbMATH Open1437.05033arXiv1912.11230OpenAlexW3099081656MaRDI QIDQ1985367FDOQ1985367

Ian M. Wanless, Darcy Best

Publication date: 7 April 2020

Published in: Algebraic Combinatorics (Search for Journal in Brave)

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 $$.

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

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

zbMATH Keywords

bipartite graphtransversalperfect matchingLatin squarepermanentparityLatin rectanglepermanental minor

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Transversals and multicolored matchings
• The number of transversals in a Latin square
• On transversals in Latin squares
• How not to prove the Alon-Tarsi conjecture
• Switching in one-factorisations of complete graphs
• The Conjectures of Alon–Tarsi and Rota in Dimension Prime Minus One
• Colorings and orientations of graphs
• Combinatorial Matrices with Small Determinants
• On even and odd latin squares
• Parity types, cycle structures and autotopisms of Latin squares
• Cycle switches in Latin squares
• On parity vectors of Latin squares
• Permanents of multidimensional matrices: Properties and applications
• Decompositions into spanning rainbow structures
• Circular designs balanced for neighbours at distances one and two
• Square-root cancellation for the signs of Latin squares
• The odd case of Rota's bases conjecture
• Parity of sets of mutually orthogonal Latin squares
• THERE ARE ASYMPTOTICALLY THE SAME NUMBER OF LATIN SQUARES OF EACH PARITY
• Graphs for Orthogonal Arrays and Projective Planes of Even Order
• Transversals in Latin Arrays with Many Distinct Symbols
• On the number of symbols that forces a transversal
• Transversals in generalized Latin squares

Cited In (4)

• Title not available (Why is that?)
• On transversals in Latin squares
• Transversals in Latin Squares
• The Bruhat order on classes of isotopic 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)