Abstract:This paper studies the probability of substructures occurring in random Latin squares. Our main result states that if $\alpha,\beta>0$ are such that $2\alpha+\beta<1$, then there are positive constants $\delta = \delta(\alpha, \beta)$ and $\Delta = \Delta(\alpha, \beta)$ such that if $P$ is a partial Latin square of order $n$ with $k = k(n)$ non-empty cells occupying at most $\alpha n$ rows and $\beta n$ columns, the probability that a random Latin square of order $n$ contains $P$ lies between $(\delta/n)^k$ and $(\Delta/n)^k$. We apply this result to subsquares in random Latin squares to obtain the first proof of the fact that the expected number of subsquares of order $3$ in a random Latin square of order $n$ is non-vanishing as $n \to \infty$. We are also able to provide the best known asymptotics for the expected number of subsquares of order $a$ in a random Latin square of order $n$ when $2<a=o(n^{1/2})$. Finally, we discuss the implications of our result on other configurations in random Latin squares as well as on completions of partial Latin squares.
From: Jack Allsop [view email]
[v1]
Tue, 16 Jun 2026 17:08:58 UTC (445 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。