Canonical Labeling of Latin Squares in Average-Case Polynomial Time

A Latin square of order (Formula presented.) is an (Formula presented.) matrix in which each row and column contains each of (Formula presented.) symbols exactly once. For (Formula presented.), we show that with high probability a uniformly random Latin square of order (Formula presented.) has no proper subsquare of order larger than (Formula presented.). Using this fact, we present a canonical labeling algorithm for Latin squares of order (Formula presented.) that runs in average time bounded by a polynomial in (Formula presented.). 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-factorizations, nets, affine planes, and projective planes.