McKay–Wanless conjecture on intercalates in random Latin squares

About 10 years old · traced to

Let L\mathcal{L} be the set of n×nn\times n Latin squares, and let L∈L\boldsymbol{L}\in\mathcal{L} be uniformly random. Let N=N(L)\boldsymbol{N}=N(\boldsymbol{L}) denote the number of intercalates in L\boldsymbol{L}. For any fixed ε>0\varepsilon>0, asymptotically almost surely,

\originalleft(1−ε\aftergroup\originalright)n24≤N≤\originalleft(1+ε\aftergroup\originalright)n24.\mathopen{}\mathclose\bgroup\originalleft(1-\varepsilon\aftergroup\egroup\originalright)\frac{n^{2}}{4}\le\boldsymbol{N}\le\mathopen{}\mathclose\bgroup\originalleft(1+\varepsilon\aftergroup\egroup\originalright)\frac{n^{2}}{4}.

McKay–Wanless conjecture. The displayed concentration holds for every fixed ε>0\varepsilon>0. This predicts that a uniformly random Latin square has approximately n2/4n^{2}/4 intercalates. The paper proves a matching lower bound asymptotically almost surely and obtains an upper bound of fn2fn^{2} for every function f→∞f\to\infty, but the sharp asymptotic upper bound remains open.

References

Primary source

Matthew Kwan and Benny Sudakov, “Intercalates and Discrepancy in Random Latin Squares”, arXiv:1607.04981 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.