Restricted completion of sparse partial Latin squares

• 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)