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.
Categories: math.CO