Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-24T00:03:56.065Z Has data issue: false hasContentIssue false

Avoiding Arrays of Odd Order by Latin Squares

Published online by Cambridge University Press:  21 December 2012

LINA J. ANDRÉN
Affiliation:
Department of Mathematics and Mathematical Statistics, Umeå University, SE-90187 Umeå, Sweden (e-mail: [email protected], [email protected])
CARL JOHAN CASSELGREN
Affiliation:
Department of Mathematics, Linköping University, SE-58183 Linköping, Sweden (e-mail: [email protected])
LARS-DANIEL ÖHMAN
Affiliation:
Department of Mathematics and Mathematical Statistics, Umeå University, SE-90187 Umeå, Sweden (e-mail: [email protected], [email protected])

Abstract

We prove that there is a constant c such that, for each positive integer k, every (2k + 1) × (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) × (2k+1) Latin square S on the symbols 1,. . .,2k+1 such that, for each i,j ∈ {1,. . .,2k+1}, the symbol in position (i,j) of S does not appear in the corresponding cell in A. This settles the last open case of a conjecture by Häggkvist. Using this result, we also show that there is a constant ρ, such that, for any positive integer n, if each cell in an n × n array B is assigned a set of m ≤ ρ 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 → ∞.

Type
Paper
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N. and Spencer, J. H. (2000) The Probabilistic Method, Wiley-Interscience.Google Scholar
[2]Andrén, L. J. (2010) On Latin squares and avoidable arrays. Doctoral thesis, Umeå University.Google Scholar
[3]Asratian, A. S., Denley, T. M. J. and Häggkvist, R. (1998) Bipartite Graphs and their Applications, Cambridge University Press.Google Scholar
[4]Brègman, L. M. (1973) Certain properties of nonnegative matrices and their permanents. Dokl. Akad. Nauk SSSR 211 2730.Google Scholar
[5]Casselgren, C. J. (2012) On avoiding some families of arrays. Discrete Math. 312 963972.Google Scholar
[6]Cavenagh, N. J. (2010) Avoidable partial Latin squares of order 4m+1. Ars Combin. 95 257275.Google Scholar
[7]Chetwynd, A. G. and Rhodes, S. J. (1997) Avoiding multiple entry arrays. J. Graph Theory 25 257266.Google Scholar
[8]Chetwynd, A. G. and Rhodes, S. J. (1997) Avoiding partial Latin squares and intricacy. Discrete Math. 177 1732.Google Scholar
[9]Csaba, B. (2007) Regular spanning subgraphs of bipartite graphs of high minimum degree. Electron. J. Combin. 14 N21.Google Scholar
[10]Cutler, J. and Öhman, L.-D. (2006) Latin squares with forbidden entries. Electron. J. Combin. 13 R47.CrossRefGoogle Scholar
[11]Häggkvist, R. (1989) A note on Latin squares with restricted support. Discrete Math. 75 253254.CrossRefGoogle Scholar
[12]Öhman, L.-D. (2011) Partial Latin squares are avoidable. Ann. Combin. 15 485497.Google Scholar