Completing Partial Latin Squares with Blocks of Non-empty Cells

详细信息    查看全文

• 作者：Jaromy Kuhl ; Michael W. Schroeder
• 关键词：Partial ; Latin square ; Completion
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：32
• 期：1
• 页码：241-256
• 全文大小：892 KB
• 参考文献：1.Anderson, L.D., Hilton, A.J.W.: Thanks Evans!. Proc. Lond. Math. Soc. 47, 507–522 (1983)CrossRef
  2.Dénes, J., Keedwell, A.: Latin Squares, Annals of Discrete Mathematics. New developments in the theory and applications, vol. 46. With contributions by G.B. Belyavskaya, A.E. Brouwer, T. Evans, K. Heinrich, C.C. Lindner, and D.A. Preece. With a foreword by Paul Erdős. North-Holland Publishing Co., Amsterdam (1991)
  3.Denley, T., Häggkvist, R.: Completing some partial Latin squares. Eur. J. Comb. 21, 877–880 (1995)CrossRef
  4.Evans, T.: Embedding incomplete Latin squares. Am. Math. Mon. 67, 958–961 (1960)CrossRef
  5.Häggkvist, R.: A solution to the Evans conjecture for Latin squares of large size. Colloqu. Math. Soc. Janos Bolyai 18, 405–513 (1978)
  6.Hall, P.: On representatives of subsets. J. Lond. Math. Soc. 10, 26–30 (1935)
  7.Hilton, A.J.W.: The reconstruction of latin squares with applications to school timetables and experimental design. Math. Progr. Study 13, 68–77 (1980)MATH CrossRef
  8.Öhman, L.-D.: A note on completing Latin squares, Australas. J. Comb. 45, 117–123 (2009)MATH
  9.Kuhl, J., Denley, T.: On a generalization of the Evans conjecture. Discret. Math. 308, 4763–4767 (2008)MATH MathSciNet CrossRef
  10.Ryser, H.J.: A combinatorial theorem with an application to Latin squares. Proc. Am. Math. Soc. 2, 550–552 (1951)MATH MathSciNet CrossRef
  11.Smetaniuk, B.: A new construction for latin squares I. Proof of the Evans conjecture. Ars Comb. 11, 155–172 (1981)MATH MathSciNet
  
• 作者单位：Jaromy Kuhl (1)
  Michael W. Schroeder (2)
  
  1. Department of Mathematics and Statistics, University of West Florida, 11000 University Parkway, Pensacola, FL, 32514, USA
  2. Department of Mathematics, Marshall University, 1 John Marshall Drive, Huntington, WV, 25755, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

In this paper we develop two methods for completing partial latin squares and prove the following. Let \(A\) be a partial latin square of order \(nr\) in which all non-empty cells occur in at most \(n-1\) \(r\times r\) squares. If \(t_1,\ldots , t_m\) are positive integers for which \(n\geqslant t_1^2+t_2^2+\cdots +t_m^2+1\) and if \(A\) is the union of \(m\) subsquares each with order \(rt_i\), then \(A\) can be completed. We additionally show that if \(n\geqslant r+1\) and \(A\) is the union of \(n\) identical \(r\times r\) squares with disjoint rows and columns, then \(A\) can be completed. For smaller values of \(n\) we show that a completion does not always exist. Keywords Partial Latin square Completion