Large deviations in random latin squares

Kwan MA, Sah A, Sawhney M. 2022. Large deviations in random latin squares. Bulletin of the London Mathematical Society.


Journal Article | Epub ahead of print | English

Scopus indexed
Author
Kwan, Matthew AlanISTA; Sah, Ashwin; Sawhney, Mehtaab
Department
Abstract
In this note, we study large deviations of the number 𝐍 of intercalates ( 2Γ—2 combinatorial subsquares which are themselves Latin squares) in a random 𝑛×𝑛 Latin square. In particular, for constant 𝛿>0 we prove that exp(βˆ’π‘‚(𝑛2log𝑛))β©½Pr(𝐍⩽(1βˆ’π›Ώ)𝑛2/4)β©½exp(βˆ’Ξ©(𝑛2)) and exp(βˆ’π‘‚(𝑛4/3(log𝑛)))β©½Pr(𝐍⩾(1+𝛿)𝑛2/4)β©½exp(βˆ’Ξ©(𝑛4/3(log𝑛)2/3)) . As a consequence, we deduce that a typical order- 𝑛 Latin square has (1+π‘œ(1))𝑛2/4 intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless.
Publishing Year
Date Published
2022-04-10
Journal Title
Bulletin of the London Mathematical Society
Acknowledgement
We thank Zach Hunter for pointing out some important typographical errors. We also thank the referee for several remarks which helped improve the paper substantially. Kwan was supported by NSF grant DMS-1953990. Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-1745302.
ISSN
eISSN
IST-REx-ID

Cite this

Kwan MA, Sah A, Sawhney M. Large deviations in random latin squares. Bulletin of the London Mathematical Society. 2022. doi:10.1112/blms.12638
Kwan, M. A., Sah, A., & Sawhney, M. (2022). Large deviations in random latin squares. Bulletin of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.12638
Kwan, Matthew Alan, Ashwin Sah, and Mehtaab Sawhney. β€œLarge Deviations in Random Latin Squares.” Bulletin of the London Mathematical Society. Wiley, 2022. https://doi.org/10.1112/blms.12638.
M. A. Kwan, A. Sah, and M. Sawhney, β€œLarge deviations in random latin squares,” Bulletin of the London Mathematical Society. Wiley, 2022.
Kwan MA, Sah A, Sawhney M. 2022. Large deviations in random latin squares. Bulletin of the London Mathematical Society.
Kwan, Matthew Alan, et al. β€œLarge Deviations in Random Latin Squares.” Bulletin of the London Mathematical Society, Wiley, 2022, doi:10.1112/blms.12638.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2106.11932

Search this title in

Google Scholar