No CrossRef data available.
Article contents
Restricted completion of sparse partial Latin squares
Published online by Cambridge University Press: 20 February 2019
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
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
Secondary:
05C15: Coloring of graphs and hypergraphs
Information
- Type
- Paper
- Information
- Copyright
- © Cambridge University Press 2019
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
You have
Access
- 3
- Cited by