Friday, April 5 2019
12:30pm - 2:00pm
Discrete Mathematics Seminar
Discrete Mathematics Seminar: JD Nir

Title: The Chromatic Number of Random Lifts of Complete Graphs

Abstract: Graph coloring is one of several constraint satisfaction problems that are studied on random structures. The problem at the heart of this talk is to identify the chromatic number of a random d-regular graph. However, inspired by an open question of Linial, instead of choosing our graph uniformly we start with the complete graph on d+1 vertices and take a random lift by replacing each vertex with an independent set and each edge with a random matching. In calculating the first and second moments we used a diverse set of tools from calculus, algebra and complex analysis. I'll focus on these techniques and where they fit into the outline of our proof.
Speaker:JD Nir
Affiliation:University of Nebraska-Lincoln

Download as iCalendar