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.

Catechol 2,3-dioxygenase-assisted cleavage of aromatics by “anaerobic” termite gut spirochetes and genomic evidence of a complete meta-pathway

The termite hindgut microbial ecosystem functions like a miniature lignocellulose-metabolizing natural bioreactor, has significant implications to nutrient cycling in the terrestrial environment, and represents an array of microbial metabolic diversity. Deciphering the intricacies of this microbial community to obtain as complete a picture as possible of how it functions as a whole, requires a combination of various traditional and cutting-edge bioinformatic, molecular, physiological, and culturing approaches. Isolates from this ecosystem, including Treponema primitia str. ZAS-1 and ZAS-2 as well as T. azotonutricium str. ZAS-9, have been significant resources for better understanding the termite system. While not all functions predicted by the genomes of these three isolates are demonstrated in vitro, these isolates do have the capacity for several metabolisms unique to spirochetes and critical to the termite system’s reliance upon lignocellulose. In this thesis, work culturing, enriching for, and isolating diverse microorganisms from the termite hindgut is discussed. Additionally, strategies of members of the termite hindgut microbial community to defend against O₂-stress and to generate acetate, the “biofuel” of the termite system, are proposed. In particular, catechol 2,3-dioxygenase and other meta-cleavage catabolic pathway genes are described in the “anaerobic” termite hindgut spirochetes T. primitia str. ZAS-1 and ZAS-2, and the first evidence for aromatic ring cleavage in the phylum (division) Spirochetes is also presented. These results suggest that the potential for O₂-dependent, yet nonrespiratory, metabolisms of plant-derived aromatics should be re-evaluated in termite hindgut communities. Potential future work is also illustrated.

Structure theorems for noncommutative complete local rings

If R is a ring with identity, let N(R) denote the Jacobson radical of R. R is local if R/N(R) is an artinian simple ring and ∩N(R)ⁱ = 0. It is known that if R is complete in the N(R)-adic topology then R is equal to (B)_n, the full n by n matrix ring over B where E/N(E) is a division ring. The main results of the thesis deal with the structure of such rings B. In fact we have the following.

If B is a complete local algebra over F where B/N(B) is a finite dimensional normal extension of F and N(B) is finitely generated as a left ideal by k elements, then there exist automorphisms g_i,...,g_k of B/N(B) over F such that B is a homomorphic image of B/N[[x₁,…,x_k;g₁,…,g_k]] the power series ring over B/N(B) in noncommuting indeterminates x_i, where x_ib = g_i(b)x_i for all b ϵ B/N.

Another theorem generalizes this result to complete local rings which have suitable commutative subrings. As a corollary of this we have the following. Let B be a complete local ring with B/N(B) a finite field. If N(B) is finitely generated as a left ideal by k elements then there exist automorphisms g₁,…,g_k of a v-ring V such that B is a homomorphic image of V [[x₁,…,x_k;g₁,…,g_k]].

In both these results it is essential to know the structure of N(B) as a two sided module over a suitable subring of B.