Large deviations in random Latin squares


Abstract in English

In this note, we study large deviations of the number $mathbf{N}$ of intercalates ($2times2$ combinatorial subsquares which are themselves Latin squares) in a random $ntimes n$ Latin square. In particular, for constant $delta>0$ we prove that $Pr(mathbf{N}le(1-delta)n^{2}/4)leexp(-Omega(n^{2}))$ and $Pr(mathbf{N}ge(1+delta)n^{2}/4)leexp(-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.

Download