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
How to do what you want to do when you can not do what you want: on avoiding and completing partial latin squares
Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
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 [en]
Latin squares, constraint satisfaction, schedulling, array,
National Category
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-867ISBN: 91-7264-143-6 (print)OAI: oai:DiVA.org:umu-867DiVA: diva2:144802
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
List of papers
1. Partial latin squares are avoidable
Open this publication in new window or tab >>Partial latin squares are avoidable
2011 (English)In: Annals of Combinatorics, ISSN 0218-0006, E-ISSN 0219-3094, Vol. 15, no 3, 485-497 p.Article in journal (Refereed) Published
Abstract [en]

A square array is avoidable if for each set of n symbols there is an n x n Latin square on these symbols which differs from the array in every cell. The main result of this paper is that for m >= 2 any partial Latin square of order 4m - 1 is avoidable, thus concluding the proof that any partial Latin square of order at least 4 is avoidable.

Keyword
Latin square, partial Latin square, avoidable array
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-5317 (URN)10.1007/s00026-011-0106-5 (DOI)
Available from: 2006-09-15 Created: 2006-09-15 Last updated: 2011-12-20Bibliographically approved
2. Latin squares with forbidden entries
Open this publication in new window or tab >>Latin squares with forbidden entries
2006 (English)In: The Electronic Journal of Combinatorics, ISSN 1077-8926, Vol. 13, no 1, R47- p.Article in journal (Refereed) Published
Identifiers
urn:nbn:se:umu:diva-5318 (URN)
Available from: 2006-09-15 Created: 2006-09-15 Last updated: 2011-03-02Bibliographically approved
3. Unavoidable arrays
Open this publication in new window or tab >>Unavoidable arrays
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.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-5319 (URN)
Available from: 2006-09-15 Created: 2006-09-15 Last updated: 2012-02-29Bibliographically approved
4. The intricacy of avoiding arrays
Open this publication in new window or tab >>The intricacy of avoiding arrays
2005 (English)Manuscript (preprint) (Other academic)
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-5320 (URN)
Available from: 2006-09-15 Created: 2006-09-15 Last updated: 2012-09-27

Open Access in DiVA

fulltext(201 kB)540 downloads
File information
File name FULLTEXT01.pdfFile size 201 kBChecksum SHA-1
75c3aad9775e2c0d0320ef6f96295bf69708cc5e15c84f30d398fdfdf6aa2c5bb006fef7
Type fulltextMimetype application/pdf

By organisation
Mathematics and Mathematical Statistics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 540 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 543 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