Restricted completion of sparse partial Latin squares

Abstract

An $n\times n$ partial Latin square $P$ is called $\alpha$-dense if each row and column has at most $\alpha n$ non-empty cells and each symbol occurs at most $\alpha n$ times in $P$. An $n\times n$ array $A$ where each cell contains a subset of $\{1,\dots ,n\}$ is a $(\beta n,\beta n,\beta n)$-array if each symbol occurs at most $\beta n$ times in each row and column and each cell contains a set of size at most $\beta n$. Combining the notions of completing partial Latin squares and avoiding arrays, we prove that there are constants $\alpha ,\beta >0$ such that, for every positive integer $n$, if $P$ is an $\alpha$-dense $n\times n$ partial Latin square, $A$ is an $n\times n$ $(\beta n,\beta n,\beta n)$-array, and no cell of $P$ contains a symbol that appears in the corresponding cell of $A$, then there is a completion of $P$ that avoids $A$; that is, there is a Latin square $L$ that agrees with $P$ on every non-empty cell of $P$, and, for each $i,j$ satisfying $1\le i,j\le n$, the symbol in position $(i,j)$ in $L$ does not appear in the corresponding cell of $A$.

19 pages