2016/07/18 by Kwan, Matthew, Sudakov, Benny · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1607.04981
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 𝔼N≤(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.