TY - JOUR
AB - 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.
AU - Kwan, Matthew Alan
AU - Sudakov, Benny
ID - 9568
IS - 2
JF - Random Structures and Algorithms
SN - 1042-9832
TI - Intercalates and discrepancy in random Latin squares
VL - 52
ER -