Sökning: id:"swepub:oai:DiVA.org:mdh-46537" >
Restricted completi...
Restricted completion of sparse partial Latin squares
-
- Andrén, Lina (författare)
- Mälardalens högskola,Malardalen Univ, Sweden; Mittag Leffler Inst, Sweden
-
- Casselgren, Carl Johan (författare)
- Linköpings universitet,Matematik och tillämpad matematik,Tekniska fakulteten,Mittag Leffler Inst, Sweden
-
- Markström, Klas (författare)
- Umeå universitet,Institutionen för matematik och matematisk statistik,Umeå University, Sweden; Mittag Leffler Inst, Djursholm, Sweden,Umea Univ, Sweden; Mittag Leffler Inst, Sweden
-
(creator_code:org_t)
- Cambridge University Press, 2019
- 2019
- Engelska.
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 28:5, s. 675-695
- Relaterad länk:
-
https://liu.diva-por... (primary) (Raw object)
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
https://urn.kb.se/re...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
Nyckelord
- Cells
- 2010 MSC Codes
- Latin square
- Partial Latin squares
- Positive integers
- Primary 05B15
- Secondary 05C15
- Cytology
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas