Georgia Institute of Technology College of Sciences

In this dissertation, we use methods of probabilistic combinatorics to work towards a conjecture of Alon and Kim about coloring the edges of k-uniform t-simple hypergraphs. A hypergraph is k-uniform if every edge contains exactly k vertices, and t-simple if any two edges intersect in at most t vertices. The chromatic index of a hypergraph H is the smallest integer N such that one can properly color the edges of H with N colors.

In 1997, Alon and Kim conjectured that if H is a k-uniform t-simple hypergraph with maximum degree D sufficiently large, then the chromatic index \chi'(H) is upper bounded by (t-1+1/t+\epsilon)D. Using probabilistic techniques and a nibble coloring method, we prove a general coloring theorem stating that a k-uniform t-simple hypergraph H with large maximum degree D has chromatic index at most (b+\epsilon)kD, where b is a particular parameter derived from local structural information about H.

We use structural techniques to prove sharp upper bounds on b in the 3-uniform 2-simple, and 3-uniform 3-simple cases. In particular, we deduce as a corollary that for sufficiently large D, every 3-uniform 2-simple and 3-simple hypergraph of maximum degree at most D has chromatic index at most 2.358D and 2.679D, respectively. We also prove that for sufficiently large D, every 3-uniform 2-simple hypergraph has fractional chromatic index at most 2D.