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.

Charles I : unhero of royalist poetry

During the English Civil War, Charles I appeared as a character in Royalist poetry, both directly and allegorically. These depictions drew on ancient Roman epic poems, particularly Lucan’s De Bello Civili, in their treatment of the subject matter of civil war and Charles as an epic hero. Though the authors of these poems supported Charles, their depictions of him and his reign reveal anxiety about his weakness as a ruler. In comparison to the cults of personality surrounding his predecessors and the heroes of De Bello Civili, his cult appears bland and forced. The lack of enthusiasm surrounding Charles I may help to explain his downfall at the hands of his Parliamentarian opponents.  

Violence in the Medieval Church before the First Crusade

The attitude of the medieval church towards violence before the First Crusade in 1095 underwent a significant institutional evolution, from the peaceful tradition of the New Testament and the Roman persecution, through the prelate-led military campaigns of the Carolingian period and the Peace of God era. It would be superficially easy to characterize this transformation as the pragmatic and entirely secular response of a growing power to the changing world. However, such a simplification does not fully do justice to the underlying theology. While church leaders from the 5th Century to the 11th had vastly different motivations and circumstances under which to develop their responses to a variety of violent activities, the teachings of Augustine of Hippo provided a unifying theme. Augustine’s just war theology, in establishing which conflicts are acceptable in the eyes of God, focused on determining whether a proper causa belli or basis for war exists, and then whether a legitimate authority declares and leads the war. Augustine masterfully integrated aspects of the Old and New Testaments to create a lasting and compelling case for his definition of justified violence. Although at different times and places his theology has been used to support a variety of different attitudes, the profound influence of his work on the medieval church’s evolving position on violence is clear.