Completions of ε-Dense Partial Latin Squares

Abstract

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.

Additional details