2012/05/07 by Padraic Bartlett, Bartlett, Padraic
Engineering · Mathematics · #graph theory and CDMA systems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1205.1558
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 will investigate the class of ≤ε-dense partial latin squares: partial latin squares in which each symbol, row, and column contains ≤εn-many nonblank cells. A conjecture of Nash-Williams on triangulations of graphs led Daykin and Häggkvist to conjecture 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 \leqdn2 cells. In particular, we establish that all ≤(1/5300)-dense n by n partial latin squares are completable, as well as all ≤(1/13)-dense n by n partial latin squares that contain ≤(8.8*10^(-5)*n2)-many filled cells. This improves prior results of Gustavsson, which required ε= d ≤ 10^(-7), as well as Chetwynd and Haggkvist, which required ε= d ≤ 10^(-5) and n even, ≤ 107.