umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Avoidability by Latin squares of arrays of even order
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik. (Diskret matematik)
(Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
Abstract [en]

We prove that for any k and any 2k × 2k array A such that no cell in A contains more than   k/2550 symbols, and no symbol occurs more than k/2550 times in any row or column, there is a Latin square such that no 2550cell in the Latin square contains a symbol that occurs in the corresponding cell in A. This proves a conjecture of Häggkvist [8] in the special case of arrays with even side.

Nyckelord [en]
Latin square, avoidability, avoidable array
Nationell ämneskategori
Diskret matematik
Forskningsämne
matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-36025OAI: oai:DiVA.org:umu-36025DiVA, id: diva2:351489
Tillgänglig från: 2010-09-15 Skapad: 2010-09-14 Senast uppdaterad: 2018-06-08Bibliografiskt granskad
Ingår i avhandling
1. On Latin squares and avoidable arrays
Öppna denna publikation i ny flik eller fönster >>On Latin squares and avoidable arrays
2010 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

This thesis consists of the four papers listed below and a survey of the research area.

I Lina J. Andrén: Avoiding (m, m, m)-arrays of order n = 2k

II Lina J. Andrén: Avoidability of random arrays

III Lina J. Andr´en: Avoidability by Latin squares of arrays with even order

IV Lina J. Andrén, Carl Johan Casselgren and Lars-Daniel Öhman: Avoiding arrays of odd order by Latin squares

Papers I, III and IV are all concerned with a conjecture by Häggkvist saying that there is a constant c such that for any positive integer n, if m ≤ cn, then for every n × n array A of subsets of {1, . . . , n} such that no cell contains a set of size greater than m, and none of the elements 1, . . . , n belongs to more than m of the sets in any row or any column of A, there is a Latin square L on the symbols 1, . . . , n such that there is no cell in L that contains a symbol that belongs to the set in the corresponding cell of A. Such a Latin square is said to avoid A. In Paper I, the conjecture is proved in the special case of order n = 2k . Paper III improves on the techniques of Paper I, expanding the proof to cover all arrays of even order. Finally, in Paper IV, similar methods are used together with a recoloring theorem to prove the conjecture for all orders. Paper II considers another aspect of the problem by asking to what extent way a deterministic result concerning the existence of Latin squares that avoid certain arrays can be used when the sets in the array are assigned randomly.

Abstract [sv]

Denna avhandling inehåller de fyra nedan uppräknade artiklarna, samt en översikt av forskningsområdet.

I Lina J. Andrén: Avoiding (m, m, m)-arrays of order n = 2k

II Lina J. Andrén: Avoidability of random arrays

III Lina J. Andrén: Avoidability by Latin squares of arrays with even order

IV Lina J. Andrén, Carl Johan Casselgren and Lars-Daniel Öhman: Avoiding arrays of odd order by Latin squares

Artikel I, III och IV behandlar en förmodan av Häggkvist, som säger att det finns en konstant c sådan att för varje positivt heltal n gäller att om m ≤ cn så finns för varje n × n array A av delmängder till {1, . . . ,n} sådan att ingen cell i A i innehåller fler än m symboler, och ingen symbol förekommer i fler än m celler i någon av raderna eller kolumnerna, så finns en latinsk kvadrat L sådan att ingen cell i L innehåller en symbol som förekommer i motsvarande cell i A. En sådan latinsk kvadrat sägs undvika A. Artikel I innehåller ett bevis av förmodan i specialfallet n = 2k. Artikel III använder och utökar metoderna i Artikel I till ett bevis av förmodan för alla latinska kvadrater av jämn ordning. Förmodan visas slutligen för samtliga ordningar i Artikel IV, där bevismetoden liknar den som finns i i Artikel I och III tillsammans med en omfärgningssats. Artikel II behandlar en annan aspekt av problemet genom att undersöka vad ett deterministiskt resultat om existens av latinska kvadrater som undviker en viss typ av array säger om arrayer där mängderna tilldelas slumpmässigt.

Ort, förlag, år, upplaga, sidor
Umeå: Umeå universitet, Instituionen för matematik och matematisk statisitik, 2010. s. 31
Serie
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 46
Nyckelord
Latin square, avoidability, avoidable array
Nationell ämneskategori
Diskret matematik
Forskningsämne
matematik
Identifikatorer
urn:nbn:se:umu:diva-36040 (URN)978-91-7459-060-9 (ISBN)
Disputation
2010-10-07, MA121, MIT-huset, Umeå universitet, Umeå, 11:04 (Svenska)
Opponent
Handledare
Tillgänglig från: 2010-09-16 Skapad: 2010-09-15 Senast uppdaterad: 2018-06-08Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Andrén, Lina J.

Sök vidare i DiVA

Av författaren/redaktören
Andrén, Lina J.
Av organisationen
Institutionen för matematik och matematisk statistik
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 667 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf