Completions of epsilon-dense partial Latin squares

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"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(1-12epsilonright)^{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 NP-complete 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 NP-complete, 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.

I. The rate and mechanism of the vapor-phase reaction between water and parts-per-million concentrations of nitrogen dioxide. II. The rate and mechanism of the air oxidation of parts-per-million concentrations of nitric oxide in the presence of water vapor.

Part I

A study of the thermal reaction of water vapor and parts-per-million concentrations of nitrogen dioxide was carried out at ambient temperature and at atmospheric pressure. Nitric oxide and nitric acid vapor were the principal products. The initial rate of disappearance of nitrogen dioxide was first order with respect to water vapor and second order with respect to nitrogen dioxide. An initial third-order rate constant of 5.5 (± 0.29) x 10⁴ liter² mole^-2 sec^-1 was found at 25˚C. The rate of reaction decreased with increasing temperature. In the temperature range of 25˚C to 50˚C, an activation energy of -978 (± 20) calories was found.

The reaction did not go to completion. From measurements as the reaction approached equilibrium, the free energy of nitric acid vapor was calculated. This value was -18.58 (± 0.04) kilocalories at 25˚C.

The initial rate of reaction was unaffected by the presence of oxygen and was retarded by the presence of nitric oxide. There were no appreciable effects due to the surface of the reactor. Nitric oxide and nitrogen dioxide were monitored by gas chromatography during the reaction.

Part II

The air oxidation of nitric oxide, and the oxidation of nitric oxide in the presence of water vapor, were studied in a glass reactor at ambient temperatures and at atmospheric pressure. The concentration of nitric oxide was less than 100 parts-per-million. The concentration of nitrogen dioxide was monitored by gas chromatography during the reaction.

For the dry oxidation, the third-order rate constant was 1.46 (± 0.03) x 10⁴ liter² mole^-2 sec^-1 at 25˚C. The activation energy, obtained from measurements between 25˚C and 50˚C, was -1.197 (±0.02) kilocalories.

The presence of water vapor during the oxidation caused the formation of nitrous acid vapor when nitric oxide, nitrogen dioxide and water vapor combined. By measuring the difference between the concentrations of nitrogen dioxide during the wet and dry oxidations, the rate of formation of nitrous acid vapor was found. The third-order rate constant for the formation of nitrous acid vapor was equal to 1.5 (± 0.5) x 10⁵ liter² mole^-2 sec^-1 at 40˚C. The reaction rate did not change measurably when the temperature was increased to 50˚C. The formation of nitric acid vapor was prevented by keeping the concentration of nitrogen dioxide low.

Surface effects were appreciable for the wet tests. Below 35˚C, the rate of appearance of nitrogen dioxide increased with increasing surface. Above 40˚C, the effect of surface was small.