Large deviations in random Latin squares

Abstract

In this note, we study large deviations of the number $\mathbf{N}$ of intercalates ($2\times 2$ combinatorial subsquares which are themselves Latin squares) in a random $n\times n$ Latin square. In particular, for constant $\delta >0$ we prove that $\mathrm{Pr}(\mathbf{N}\le (1-\delta )n^2/4)\le \exp (-\Omega (n^2))$ and $\mathrm{Pr}(\mathbf{N}\ge (1+\delta )n^2/4)\le \exp (-\Omega (n^{4/3}(\log n{)}^{2/3}))$, both of which are sharp up to logarithmic factors in their exponents. As a consequence, we deduce that a typical order-$n$ Latin square has $(1+o(1))n^2/4$ intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless.

arXiv comment15 pages