On the Threshold Problem for Latin Boxes

Abstract

Let $m\le n\le k$. An $m\times n\times k$ 0-1 array is a Latin box if it contains exactly $mn$ ones, and has at most one $1$ in each line. As a special case, Latin boxes in which $m=n=k$ are equivalent to Latin squares. Let $\mathcal{M}(m,n,k;p)$ be the distribution on $m\times n\times k$ 0-1 arrays where each entry is $1$ with probability $p$, independently of the other entries. The threshold question for Latin squares asks when $\mathcal{M}(n,n,n;p)$ contains a Latin square with high probability. More generally, when does $\mathcal{M}(m,n,k;p)$ support a Latin box with high probability? Let $\epsilon >0$. We give an asymptotically tight answer to this question in the special cases where $n=k$ and $m\le \left(1-\epsilon \right)n$, and where $n=m$ and $k\ge \left(1+\epsilon \right)n$. In both cases, the threshold probability is $\hat{I}˜\left(\log \left(n\right)/n\right)$. This implies threshold results for Latin rectangles and proper edge-colorings of $K_{n,n}$.

Corrected typos; Added acknowledgment