All Title Author
Keywords Abstract


Unavoidable arrays

Full-Text   Cite this paper   Add to My Lib

Abstract:

An $n imes n$ array is emph{avoidable} if for each set of $n$ symbols there is a Latin square on these symbols which differs from the array in every cell. We characterise all unavoidable square arrays with at most 2 symbols, and all unavoidable arrays of order at most 4. We also identify a number of general families of unavoidable arrays, which we conjecture to be a complete account of unavoidable arrays. Next, we investigate arrays with multiple entries in each cell, and identify a number of families of unavoidable multiple entry arrays. We also discuss fractional Latin squares, and their connections to unavoidable arrays. We note that when rephrasing our results as edge list-colourings of complete bipartite graphs, we have a situation where the lists of available colours are shorter than the length guaranteed by Galvin's theorem to allow proper colourings.

Full-Text

comments powered by Disqus