Large deviations in random latin squares. Issue 4 (10th April 2022)

• Record Type: Journal Article
• Authors: Kwan, Matthew; Sah, Ashwin; Sawhney, Mehtaab
• Is Part Of: Bulletin of the London Mathematical Society. Volume 54:Issue 4(2022)
• Page Start: 1420
• Page End: 1438
• Publication Date: 2022-04-10
• Subjects: Mathematics -- Periodicals; 510
• DOI: 10.1112/blms.12638
• Languages: English
• ISSNs: 0024-6093

Abstract

Abstract: In this note, we study large deviations of the number N $\mathbf {N}$ of intercalates ( 2 × 2 $2\times 2$ combinatorial subsquares which are themselves Latin squares) in a random n × n $n\, {\times}\, n$ Latin square. In particular, for constant δ > 0 $\delta >0$ we prove that exp ( − O ( n 2 log n ) ) ⩽ Pr ( N ⩽ ( 1 − δ ) n 2 / 4 ) ⩽ exp ( − Ω ( n 2 ) ) $\exp (-O(n^{2}\log n))\leqslant \Pr (\mathbf {N}\leqslant (1-\delta )n^{2}/4)\leqslant \exp (-\Omega (n^{2}))$ and exp ( − O ( n 4 / 3 ( log n ) ) ) ⩽ Pr ( N ⩾ ( 1 + δ ) n 2 / 4 ) ⩽ exp ( − Ω ( n 4 / 3 ( log n ) 2 / 3 ) ) $\exp (-O(n^{4/3}(\log n)))\leqslant \Pr (\mathbf {N}\geqslant (1+\delta )n^{2}/4)\leqslant \exp (-\Omega (n^{4/3}(\log n)^{2/3}))$ . As a consequence, we deduce that a typical order‐ n $n$ Latin square has ( 1 + o ( 1 ) ) n 2 / 4 $(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.