Back to search

Georgia Institute of Technology

Edge-coloring k-uniform hypergraphs of large maximum degree

Abstract

dc:description.abstract

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$, 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

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Frederickson, Sarah. Edge-coloring k-uniform hypergraphs of large maximum degree. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/81744