Canonical labelling of Latin squares in average-case polynomial time

Abstract

A Latin square of order $n$ is an $n\times n$ matrix in which each row and column contains each of $n$ symbols exactly once. For $\epsilon >0$, we show that with high probability a uniformly random Latin square of order $n$ has no proper subsquare of order larger than $n^{1/2}{\log }^{1/2+\epsilon }n$. Using this fact we present a canonical labelling algorithm for Latin squares of order $n$ that runs in average time bounded by a polynomial in $n$. The algorithm can be used to solve isomorphism problems for many combinatorial objects that can be encoded using Latin squares, including quasigroups, Steiner triple systems, Mendelsohn triple systems, $1$-factorisations, nets, affine planes and projective planes.

New reference added, minor typos fixed