umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Unavoidable arrays
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2010 (English)In: Contributions to Discrete Mathematics, ISSN 1715-0868, Vol. 5, no 1, 90-106 p.Article in journal (Refereed) Published
Abstract [en]

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.
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-5319OAI: oai:DiVA.org:umu-5319DiVA: diva2:144800
Available from: 2006-09-15 Created: 2006-09-15 Last updated: 2012-02-29Bibliographically approved
In thesis
1. How to do what you want to do when you can not do what you want: on avoiding and completing partial latin squares
Open this publication in new window or tab >>How to do what you want to do when you can not do what you want: on avoiding and completing partial latin squares
2006 (English)Doctoral thesis, comprehensive summary (Other academic)
Place, publisher, year, edition, pages
Umeå: Matematik och matematisk statistik, 2006. 9 p.
Series
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 1102-8300
Keyword
Latin squares, constraint satisfaction, schedulling, array,
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-867 (URN)91-7264-143-6 (ISBN)
Public defence
2006-10-06, MA 121, MIT-huset, Umeå universitet, Umeå, 10:15
Opponent
Supervisors
Available from: 2006-09-15 Created: 2006-09-15Bibliographically approved

Open Access in DiVA

No full text

Other links

http://cdm.math.ca/index.php/cdm/issue/view/27

Authority records BETA

Markström, KlasÖhman, Lars-Daniel

Search in DiVA

By author/editor
Markström, KlasÖhman, Lars-Daniel
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Contributions to Discrete Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 106 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf