Intercalates and discrepancy in random Latin squares

Kwan MA, Sudakov B. 2018. Intercalates and discrepancy in random Latin squares. Random Structures and Algorithms. 52(2), 181–196.


Journal Article | Published | English

Scopus indexed
Author
Abstract
An intercalate in a Latin square is a 2×2 Latin subsquare. Let N be the number of intercalates in a uniformly random n×n Latin square. We prove that asymptotically almost surely N≥(1−o(1))n2/4, and that EN≤(1+o(1))n2/2 (therefore asymptotically almost surely N≤fn2 for any f→∞). This significantly improves the previous best lower and upper bounds. We also give an upper tail bound for the number of intercalates in two fixed rows of a random Latin square. In addition, we discuss a problem of Linial and Luria on low-discrepancy Latin squares.
Publishing Year
Date Published
2018-03-01
Journal Title
Random Structures and Algorithms
Volume
52
Issue
2
Page
181-196
ISSN
eISSN
IST-REx-ID

Cite this

Kwan MA, Sudakov B. Intercalates and discrepancy in random Latin squares. Random Structures and Algorithms. 2018;52(2):181-196. doi:10.1002/rsa.20742
Kwan, M. A., & Sudakov, B. (2018). Intercalates and discrepancy in random Latin squares. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.20742
Kwan, Matthew Alan, and Benny Sudakov. “Intercalates and Discrepancy in Random Latin Squares.” Random Structures and Algorithms. Wiley, 2018. https://doi.org/10.1002/rsa.20742.
M. A. Kwan and B. Sudakov, “Intercalates and discrepancy in random Latin squares,” Random Structures and Algorithms, vol. 52, no. 2. Wiley, pp. 181–196, 2018.
Kwan MA, Sudakov B. 2018. Intercalates and discrepancy in random Latin squares. Random Structures and Algorithms. 52(2), 181–196.
Kwan, Matthew Alan, and Benny Sudakov. “Intercalates and Discrepancy in Random Latin Squares.” Random Structures and Algorithms, vol. 52, no. 2, Wiley, 2018, pp. 181–96, doi:10.1002/rsa.20742.
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 IST Research Explorer

Sources

arXiv 1607.04981

Search this title in

Google Scholar