Avoiding pairs of partial Latin squares (Q2014720): Difference between revisions

A set of partial Latin squares of order \(n\) is avoidable if there is a Latin square of order \(n\) that does not agree with any of the partial Latin squares in any cell. The authors show that if \(k>m^3(m^2-1)/2\) and \(m\geq4\) then any two partial Latin squares of order \(mk\) are avoidable (they also improve this result somewhat when \(m=4\)). When the paper was written, this was the only result showing avoidability of more than one partial Latin square of odd order. However, during the years that the paper took to appear it has been superseded by the much more general results of \textit{L. J. Andrén} et al. [Comb. Probab. Comput. 22, No. 2, 184--212 (2013; Zbl 1260.05020)]. A natural context where avoidability of Latin squares arises is in adding layers to Latin cuboids, trying to build a Latin cube. In this context, it is known [\textit{D. Bryant} et al., SIAM J. Discrete Math. 26, No. 1, 239--249 (2012; Zbl 1246.05027)] that there are sets of \(n/2+O(1)\) Latin squares of order \(n\) that are not avoidable. For partial Latin squares, it is possible [\textit{J. Cutler} and \textit{L.-D. Öhman}, Electron. J. Comb. 13, No. 1, Research paper R47, 9 p. (2006; Zbl 1098.05016)] to find sets of size \(n/3+O(1)\) that are unavoidable. There is still a large gap between these constructions and the results mentioned above.