Canonical labelling of Latin squares in average-case polynomial time

A Latin square of order n is an n n matrix in which each row and column contains each of n symbols exactly once. For >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^1/2+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.