Avoidability of random arrays

• An n×n array that in each cell contains a subset of the symbols 1, . . . , n is avoidable if there exists a Latin square of order n such that no cell in the Latin square contains a symbol which belongs to the set of symbols in the corresponding cell of the array. Some results on deterministic conditions for avoidability of arrays have been found, but here we study the problem of having an array with randomly assigned subsets of C in its cells. This is equivalent to the problem of list-edge-coloring  with randomly assigned lists from the set {1, . . . , n}. We show that an array where each symbol appears in each cell with probability p will be avoidable with very high probability even if p is such that the expected number of symbols forbidden in each cell is slightly higher than what deterministic theorems can prove is avoidable.

Subject headings

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

Keyword

Latin square

avoidable array

avoidability

Discrete mathematics

Diskret matematik

Mathematics

matematik

Publication and Content Type

vet (subject category)

ovr (subject category)