Universal probability bounds for partial Latin squares

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.

arXiv commentMinor typos corrected and one proof elaborated on