On avoiding some families of arrays

An n×nn×n array AA with entries from {1,…,n}{1,…,n} is avoidable   if there is an n×nn×n Latin square LL such that no cell in LL contains a symbol that occurs in the corresponding cell in AA. We show that the problem of determining whether an array that contains at most two entries per cell is avoidable is NPNP-complete, even in the case when the array has entries from only two distinct symbols. Assuming that P≠NPP≠NP, this disproves a conjecture by Öhman. Furthermore, we present several new families of avoidable arrays. In particular, every single entry array (arrays where each cell contains at most one symbol) of order n≥2kn≥2k with entries from at most kk distinct symbols and where each symbol occurs in at most n−2n−2 cells is avoidable, and every single entry array of order nn, where each of the symbols 1,…,n1,…,n occurs in at most ⌊n5⌋ cells, is avoidable. Additionally, if k≥2k≥2, then every single entry array of order at least n≥4n≥4, where at most kk rows contain non-empty cells and where each symbol occurs in at most n−k+1n−k+1 cells, is avoidable.