Subsquares in random Latin rectangles

Abstract

Suppose that $k$ is a function of $n$ and $n\to \infty$. We show that with probability $1-O(1/n)$, a uniformly random $k\times n$ Latin rectangle contains no proper Latin subsquare of order $4$ or more, proving a conjecture of Divoux, Kelly, Kennedy and Sidhu. We also show that the expected number of subsquares of order 3 is bounded and find that the expected number of subsquares of order 2 is $\left(\genfrac{}{}{0ex}{}{k}{2}\right)(1/2+o(1))$ for all $k\le n$.