Parity of transversals of Latin squares

Abstract

We introduce a notion of parity for transversals, and use it to show that in Latin squares of order $2\mathrm{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\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}\mathrm{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_{ab}$ mod 2. We conjecture that $t_{ac}+t_{bc}+t_{ad}+t_{bd}\equiv 0\mathrm{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 $2n$ vertices is divisible by $4$ when $n$ is odd and $k\equiv 0\mathrm{mod}4$. We also show that $$\mathrm{per}A(a\mid c)+\mathrm{per}A(b\mid c)+\mathrm{per}A(a\mid d)+\mathrm{per}A(b\mid d)\equiv 0\mathrm{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\mathrm{mod}4$.