Universal probability bounds for partial Latin squares

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 $\mathrm{\Delta }=\mathrm{\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 \mathrm{/}n{)}^k$ and $(\mathrm{\Delta }\mathrm{/}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 \mathrm{\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\mathrm{/}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.