Avoiding $(m,m,m)$-Arrays of Order $n=2^k$

Abstract

An $(m,m,m)$-array of order $n$ is an $n\times n$ array such that each cell is assigned a set of at most $m$ symbols from $\left\{1,\dots ,n\right\}$ such that no symbol occurs more than $m$ times in any row or column. An $ (m,m,m)$-array is called avoidable if there exists a Latin square such that no cell in the Latin square contains a symbol that also belongs to the set assigned to the corresponding cell in the array. We show that there is a constant $\gamma $ such that if $m\le\gamma 2^k$ and $k\ge14$, then any $(m,m,m)$-array of order $n=2^k$ is avoidable. Such a constant $\gamma$ has been conjectured to exist for all $n$ by Häggkvist.