Citation
Bartlett, Padraic James (2013) Completions of epsilondense partial Latin squares. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:06032013015803040
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 textbf{$epsilon$dense partial Latin squares}: partial Latin squares in which each symbol, row, and column contains no more than $epsilon n$many nonblank cells. Based on a conjecture of NashWilliams, Daykin and H"aggkvist conjectured that all $frac{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 novel technique to study $ epsilon$dense partial Latin squares that contain no more than $delta n^2$ filled cells in total.
In Chapter 2, we construct completions for all $ epsilon$dense partial Latin squares containing no more than $delta n^2$ filled cells in total, given that $epsilon < frac{1}{12}, delta < frac{ left(112epsilonright)^{2}}{10409}$. In particular, we show that all $9.8 cdot 10^{5}$dense partial Latin squares are completable. In Chapter 4, we augment these results by roughly a factor of two using some probabilistic techniques. These results improve prior work by Gustavsson, which required $epsilon = delta leq 10^{7}$, as well as Chetwynd and H"aggkvist, which required $epsilon = delta = 10^{5}$, $n$ even and greater than $10^7$.
If we omit the probabilistic techniques noted above, we further show that such completions can always be found in polynomial time. This contrasts a result of Colbourn, which states that completing arbitrary partial Latin squares is an NPcomplete task. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary $left(frac{1}{2} + epsilonright)$dense partial Latin square is NPcomplete, for any $epsilon > 0$.
Colbourn's result hinges heavily on a connection between triangulations of tripartite graphs and Latin squares. Motivated by this, we use our results on Latin squares to prove that any tripartite graph $G = (V_1, V_2, V_3)$ such that begin{itemize} item $V_1 = V_2 = V_3 = n$, item For every vertex $v in V_i$, $deg_+(v) = deg_(v) geq (1 epsilon)n,$ and item $E(G) > (1  delta)cdot 3n^2$ end{itemize} admits a triangulation, if $epsilon < frac{1}{132}$, $delta < frac{(1 132epsilon)^2 }{83272}$. In particular, this holds when $epsilon = delta=1.197 cdot 10^{5}$.
This strengthens results of Gustavsson, which requires $epsilon = delta = 10^{7}$.
In an unrelated vein, Chapter 6 explores the class of textbf{quasirandom graphs}, a notion first introduced by Chung, Graham and Wilson cite{chung1989quasi} in 1989. Roughly speaking, a sequence of graphs is called "quasirandom"' if it has a number of properties possessed by the random graph, all of which turn out to be equivalent. In this chapter, we study possible extensions of these results to random $k$edge colorings, and create an analogue of Chung, Graham and Wilson's result for such colorings.
Item Type:  Thesis (Dissertation (Ph.D.)) 

Subject Keywords:  Latin squares, partial Latin squares, quasirandom graphs 
Degree Grantor:  California Institute of Technology 
Division:  Physics, Mathematics and Astronomy 
Major Option:  Mathematics 
Thesis Availability:  Public (worldwide access) 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  28 May 2013 
Record Number:  CaltechTHESIS:06032013015803040 
Persistent URL:  http://resolver.caltech.edu/CaltechTHESIS:06032013015803040 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  7819 
Collection:  CaltechTHESIS 
Deposited By:  Padraic Bartlett 
Deposited On:  06 Jun 2013 19:00 
Last Modified:  27 Mar 2015 16:44 
Thesis Files

PDF
 Final Version
See Usage Policy. 762Kb 
Repository Staff Only: item control page