Row-Hamiltonian Latin squares and perfect 1-factorisations

Jack Allsop

Monash University

October 12, 2023, 12:20 in S6


A Latin square of order $n$ is an $n \times n$ matrix of $n$ symbols, such that each symbol occurs exactly once in each row and column. Let $L$ be a Latin square of order $n$. Each pair of distinct rows of $L$ forms a $2$-line permutation. If this permutation is a single $n$-cycle, for any choice of rows, then $L$ is called row-Hamiltonian. Each Latin square has six conjugate Latin squares, obtained by uniformly permuting the coordinates of its $(\text{row}, \text{column}, \text{symbol})$ triples. Let $\nu(L)$ denote the number of conjugates of $L$ which are row-Hamiltonian. It is known that $\nu(L) \in \{0, 2, 4, 6\}$ and for each $m \in \{0, 2, 6\}$ there are known infinite families of Latin squares with $\nu = m$. We construct the first known infinite family of Latin squares with $\nu=4$.

A $1$-factorisation of a graph is a partition of its edge set into $1$-factors. A $1$-factorisation is perfect if the union of edges in any pair of its $1$-factors forms a Hamiltonian cycle. A perfect $1$-factorisation of the complete bipartite graph $K_{n, n}$ is equivalent to a row-Hamiltonian Latin square of order $n$. Our family of Latin squares with $\nu=4$ allows us to build the eighth known infinite family of perfect $1$-factorisations of complete bipartite graphs.