Avoiding Arrays of Odd Order by Latin Squares

• We prove that there is a constant c such that, for each positive integer k, every (2k + 1) x (2k + 1) array A on the symbols 1, ... , 2k + 1 with at most c(2k + 1) symbols in every cell, and each symbol repeated at most c(2k + 1) times in every row and column is avoidable; that is, there is a (2k + 1) x (2k + 1) Latin square S on the symbols 1, ... , 2k + 1 such that, for each i, j is an element of {1, ... , 2k + 1}, the symbol in position (i, j) of S does not appear in the corresponding cell in Lambda. This settles the last open case of a conjecture by Haggkvist. Using this result, we also show that there is a constant rho, such that, for any positive integer n, if each cell in an n x n array B is assigned a set of m andlt;= rho n symbols, where each set is chosen independently and uniformly at random from {1, ... , n}, then the probability that B is avoidable tends to 1 as n -andgt; infinity.

Subject headings

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

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

Keyword

MATHEMATICS

MATEMATIK

Publication and Content Type

ref (subject category)

art (subject category)