Completions of epsilon-dense partial Latin squares; quasirandom k-colorings of graphs

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 Nash-Williams, Daykin and Häggkvist 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 particular, 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(1-12\epsilon \right)}^2}{10409}$. In particular, we show that all $9.8\cdot 10^{-5}$-dense partial Latin squares are completable. We further show that such completions can always be found in polynomial time. This contrasts a result of Colbourn. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary $\left(\frac{1}{2}+\epsilon \right)$-dense partial Latin square is NP-complete, for any $\epsilon >0$. Additional results on triangulations of graphs are found. In an unrelated vein, Chapter 6 explores the class of quasirandom graphs. In specific, we study quasirandom $k$-edge colorings, and create an analogue of Chung, Graham and Wilson's well-known results for such colorings.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1205.1558

References in corpus (2)

• On generalised Paley graphs and their automorphism groups
• The Poset of Hypergraph Quasirandomness