Georgia Institute of Technology
Edge-coloring k-uniform hypergraphs of large maximum degree
Abstract
dc:description.abstractIn 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$, denoted $\chi'(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+ε)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+ε)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$.
Degree
thesis:*- Name thesis:degree_name
- Mathematics, PhD
- Department thesis:degree_department
- Mathematics
- Grantor
- Georgia Institute of Technology
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Frederickson, Sarah
- Advisor dc:contributor.advisor
-
- Kelly, Tom
- Committee members dc:contributor.committeemember
-
- Yu, Xingxing
- Yu, Josephine
- McCarty, Rose
- Anton Bernshteyn
Rights
- Language dc:language.iso
- English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/81744