Umeå universitets logga

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

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • 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
Restricted completion of sparse partial Latin squares
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2019 (Engelska)Ingår i: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 28, nr 5, s. 675-695Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

An n × n partial Latin square P is called α-dense if each row and column has at most αn non-empty cells and each symbol occurs at most αn times in P. An n × n array A where each cell contains a subset of {1,…, n} is a (βn, βn, βn)-array if each symbol occurs at most βn times in each row and column and each cell contains a set of size at most βn. Combining the notions of completing partial Latin squares and avoiding arrays, we prove that there are constants α, β > 0 such that, for every positive integer n, if P is an α-dense n × n partial Latin square, A is an n × n (βn, βn, βn)-array, and no cell of P contains a symbol that appears in the corresponding cell of A, then there is a completion of P that avoids A; that is, there is a Latin square L that agrees with P on every non-empty cell of P, and, for each i, j satisfying 1 ≤ i, j ≤ n, the symbol in position (i, j) in L does not appear in the corresponding cell of A.

Ort, förlag, år, upplaga, sidor
Cambridge University Press, 2019. Vol. 28, nr 5, s. 675-695
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-166828DOI: 10.1017/S096354831800055XISI: 000500255000002Scopus ID: 2-s2.0-85061937683OAI: oai:DiVA.org:umu-166828DiVA, id: diva2:1382456
Tillgänglig från: 2020-01-03 Skapad: 2020-01-03 Senast uppdaterad: 2023-03-23Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Markström, Klas

Sök vidare i DiVA

Av författaren/redaktören
Markström, Klas
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Combinatorics, probability & computing
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

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

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • 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