Next Talk

 The Chromatic Index of 3-Uniform 3-Partite Random Hypergraphs

Mason Shurman 

December 1st, 2025 (Monday) at 3pm - NSII 1201

Abstract

The \textit{chromatic index} of a graph, denoted \(\chi'(G)\), is the minimum number of colors required to color its edges such that no two edges of the same color share a vertex. Vizing's theorem, a classical result in graph theory, states that the chromatic index of a graph is either $\Delta(G)$ or $\Delta(G)+1$, where $\Delta(G)$ is the maximum number of edges that lie on any vertex.  It is natural to extend the notion of chromatic index to hypergraphs, where edges may contain more than two vertices. For hypergraphs, Vizing's theorem does not always hold: it is possible to construct examples with much larger chromatic index than the maximum degree. We show that this is not usually the case: for the random hypergraph $H \sim H^3_{n,1/2}$, with $n$ vertices where each possible $3$-edge is included with probability $1/2$, with high probability $\chi'(H)=\Delta(H)$. For the sake of brevity and clarity, this talk will mostly focus on a slightly simpler case: random $3$-partite $3$-uniform hypergraphs, where we also show that the chromatic index equals the maximum degree. This work is joint with Asaf Ferber, Marcelo Sales, and Arnab Chaterjee.

About the Speaker

Mason Shurman is a 4th year PhD student studying under Asaf Ferber. His research interests include random graphs, combinatorial games, and other areas of discrete math. In his free time, Mason loves to play piano and go rock climbing.