Intercalates and discrepancy in random Latin squares. Issue 2 (8th November 2017)

• Record Type: Journal Article
• Authors: Kwan, Matthew; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 52:Issue 2(2018)
• Page Start: 181
• Page End: 196
• Publication Date: 2017-11-08
• Subjects: discrepancy -- intercalate -- Latin square; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20742
• Languages: English
• ISSNs: 1042-9832

Abstract

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 ) ) n 2 / 4, and that E N ≤ ( 1 + o ( 1 ) ) n 2 / 2 (therefore asymptotically almost surely N ≤ f n 2 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 2 fixed rows of a random Latin square. In addition, we discuss a problem of Linial and Luria on low‐discrepancy Latin squares.