| 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 ¼-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 ε-dense partial Latin squares that contain no more than δn2 filled cells in total.;In Chapter 2, we construct completions for all ε-dense partial Latin squares containing no more than δn2 filled cells in total, given that ε < 112 , δ < 1-12e2 10409 . In particular, we show that all 9.8·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 ε = δ ≤ 10 –7, as well as Chetwynd and Häggkvist, which required ε = δ = 10–5, n even and greater than 107.;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 NP-complete task. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary (½ + ε)-dense partial Latin square is NP-complete, for any ε > 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 = ( V1, V2, V 3) such that • |V1| = |V 2| = |V3| = n, • For every vertex v ∈ Vi, deg +(v) = deg_ (v) ≥ (1 – ε) n, and • |E(G)| > (1 – δ) · 3n2 admits a triangulation, if ε < 1132 , δ < 1-132e 283272 . In particular, this holds when ε = δ = 1.197 · 10–5.;This strengthens results of Gustavsson, which requires ε = δ = 10–7.;In an unrelated vein, Chapter 6 explores the class of quasirandom graphs, a notion first introduced by Chung, Graham and Wilson [8] 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. |
