Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-23T02:53:57.771Z Has data issue: false hasContentIssue false
  • English
  • Français

Restricted completion of sparse partial Latin squares

Part of: Graph theory Designs and configurations

Published online by Cambridge University Press:  20 February 2019

Lina J. Andrén ,
Carl Johan Casselgren  and
Klas Markström
Lina J. Andrén
Affiliation:
University Library, Mälardalen University, SE-721 23 Västerås, Sweden
Carl Johan Casselgren*
Affiliation:
Department of Mathematics, Linköping University, SE-581 83 Linköping, Sweden
Klas Markström
Affiliation:
Department of Mathematics and Mathematical Statistics, Umeå University, SE-901 87 Umeå, Sweden
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

MSC classification

Primary: 05B15: Orthogonal arrays, Latin squares, Room squares
Secondary: 05C15: Coloring of graphs and hypergraphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 5 , September 2019 , pp. 675 - 695
Copyright
© Cambridge University Press 2019 

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

Footnotes

†

Part of the work done while the author was a postdoctoral researcher at the Mittag-Leffler Institute. Research supported by a postdoctoral grant from the Mittag-Leffler Institute.

‡

Part of the work done while the author was a postdoctoral researcher at the Mittag-Leffler Institute. Research supported by a postdoctoral grant from the Mittag-Leffler Institute.

§

Part of the work done while the author was visiting the Mittag-Leffler Institute. Research supported by the Mittag-Leffler Institute.

References

Adams, P., Bryant, D. and Buchanan, M. (2008) Completing partial Latin squares with two filled rows and two filled columns. Electron. J. Combin. 15 #R56.Google Scholar
Andersen, L. D. and Hilton, A. J. W. (1983) Thank Evans! Proc. London Math. Soc. 47 507–522.CrossRefGoogle Scholar
Andrén, L. J. (2010) On Latin squares and avoidable arrays. Doctoral thesis, Umeå University.Google Scholar
Andrén, L. J., Casselgren, C. J. and Öhman, L.-D. (2013) Avoiding arrays of odd order by Latin squares. Combin. Probab. Comput. 22 184–212.CrossRefGoogle Scholar
Asratian, A. S., Denley, T. M. J. and Häggkvist, R. (1998) Bipartite Graphs and Their Applications, Cambridge University Press.CrossRefGoogle Scholar
Barber, B., Kühn, D., Lo, A., Osthus, D. and Taylor, A. (2017) Clique decompositions of multipartite graphs and completion of Latin squares. J. Combin. Theory Ser. A 151 146–201.CrossRefGoogle Scholar
Bartlett, P. (2013) Completions of ɛ-dense partial Latin squares. J. Combin. Designs 21 447–463.CrossRefGoogle Scholar
Brègman, L. M. (1973) Certain properties of nonnegative matrices and their permanents. Dokl. Akad. Nauk SSSR 211 27–30.Google Scholar
Casselgren, C. J. (2012) On avoiding some families of arrays. Discrete Math. 312 963–972.CrossRefGoogle Scholar
Casselgren, C. J. and Häggkvist, R. (2013) Completing partial Latin squares with one filled row, column and symbol. Discrete Math. 313 1011–1017.CrossRefGoogle Scholar
Cavenagh, N. (2010) Avoidable partial Latin squares of order 4m + 1. Ars Combinatoria 95 257–275.Google Scholar
Chetwynd, A. G. and Häggkvist, R. (1984) Completing partial n × n Latin squares where each row, column and symbol is used at most cn times. Research report, Department of Mathematics, Stockholm University.Google Scholar
Chetwynd, A. G. and Rhodes, S. J. (1995) Chessboard squares. Discrete Math. 141 47–59.CrossRefGoogle Scholar
Chetwynd, A. G. and Rhodes, S. J. (1997) Avoiding partial Latin squares and intricacy. Discrete Math. 177 17–32.CrossRefGoogle Scholar
Chetwynd, A. G. and Rhodes, S. J. (1997) Avoiding multiple entry arrays. J. Graph Theory 25 257–266.3.0.CO;2-J>CrossRefGoogle Scholar
Colbourn, C. J. (1984) The complexity of completing partial Latin squares. Discrete Appl. Math. 8 25–30.CrossRefGoogle Scholar
Cutler, J. and Öhman, L.-D. (2006) Latin squares with forbidden entries. Electron. J. Combin. 13 #R47.Google Scholar
Daykin, D. E. and Häggkvist, R. (1984) Completion of sparse partial Latin squares. In Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference in Honour of Paul Erdös, Academic Press, pp. 127–132.Google Scholar
Denley, T. and Kuhl, J. (2012) Constrained completion of partial Latin squares. Discrete Math. 312 1251–1256.Google Scholar
Evans, T. (1960) Embedding incomplete Latin squares. Amer. Math. Monthly 67 958–961.CrossRefGoogle Scholar
Gustavsson, T. (1991) Decompositions of large graphs and digraphs with high minimum degree. Doctoral thesis, Stockholm University.Google Scholar
Häggkvist, R. (1989) A note on Latin squares with restricted support. Discrete Math. 75 253–254.CrossRefGoogle Scholar
Häggkvist, R. Personal communication.Google Scholar
Kuhl, J. S. and Schroeder, M. (2016) Completing partial Latin squares with one nonempty row, column, and symbol. Electron. J. Combin. 23 #P2.23.Google Scholar
Markström, K. and Öhman, L.-D. (2009) Unavoidable arrays. Contrib. Discrete Math. 5 90–106.Google Scholar
Öhman, L.-D. (2011) Partial Latin squares are avoidable. Ann. Combin. 15 485–497.CrossRefGoogle Scholar
Öhman, L.-D. (2011) Latin squares with prescriptions and restrictions. Austral. J. Combin. 51 77–87.Google Scholar
Ryser, H. J. (1951) A combinatorial theorem with an application to Latin rectangles. Proc. Amer. Math. Soc. 2 550–552.CrossRefGoogle Scholar
Smetaniuk, B. (1981) A new construction for Latin squares, I: Proof of the Evans conjecture. Ars Combinatoria 11 155–172.Google Scholar
Wanless, I. (2002) A generalization of transversals for Latin squares. Electron. J. Combin. 2 #R12.Google Scholar