2010 (English)In: Contributions to Discrete Mathematics, ISSN 1715-0868, Vol. 5, no 1, 90-106 p.Article in journal (Refereed) Published
An n x n array is avoidable if for each set of n symbols there is a Latin square on these symbols which diers 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.
Place, publisher, year, edition, pages
2010. Vol. 5, no 1, 90-106 p.
Research subject Mathematics
IdentifiersURN: urn:nbn:se:umu:diva-5319OAI: oai:DiVA.org:umu-5319DiVA: diva2:144800