A Caltech Library Service

Completions of ε-Dense Partial Latin Squares

Bartlett, Padraic (2013) Completions of ε-Dense Partial Latin Squares. Journal of Combinatorial Designs, 21 (10). pp. 447-463. ISSN 1063-8539. doi:10.1002/jcd.21355.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


A classical question in combinatorics is the following: given a partial Latin square P, when can we complete P to a Latin square L? In this paper, we investigate the class of ε-dense partial Latin squares: partial Latin squares in which each symbol, row, and column contains no more than ε n-many nonblank cells. Based on a conjecture of Nash-Williams, Daykin and Häggkvist conjectured that all 1/4-dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this technique to study ε-dense partial Latin squares that contain no more than δn^2 filled cells in total. In this paper, we construct completions for all ε-dense partial Latin squares containing no more than δn^2 filled cells in total, given that ε < 1/12, δ < (1-12ε)^2/10,409. In particular, we show that all 9.8 • 10^(-5)-dense partial Latin squares are completable. These results improve prior work by Gustavsson, which required ε = δ ≤ 10^(-7), as well as Chetwynd and Häggkvist, which required ε = δ = 10^(-5), n even and greater than 10^7.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2013 Wiley Periodicals, Inc. Received May 7, 2012; revised May 9, 2013. Article first published online: 10 Jun. 2013. We thank Richard Wilson for his advice throughout the research process, as well as Peter Dukes and Esther Lamken for several remarkably useful discussions. As well, thanks go to Andre Arsian, Alan Taimage, and Sachi Hashimoto for detecting errors and helping develop part of Lemma 2.1 Finally, thanks go to the referees for their thoughtful comments and assistance.
Subject Keywords:Latin squares; partial Latin squares; Häggkvist; Gustavsson; improper Latin squares; epsilon-dense partial Latin squares
Issue or Number:10
Record Number:CaltechAUTHORS:20131007-080411892
Persistent URL:
Official Citation:Bartlett, P. (2013), Completions of ε-Dense Partial Latin Squares. J. Combin. Designs, 21: 447–463. doi: 10.1002/jcd.21355
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:41698
Deposited By: Tony Diaz
Deposited On:07 Oct 2013 17:22
Last Modified:10 Nov 2021 04:33

Repository Staff Only: item control page