Friday, April 5 2019

12:30pm - 2:00pm

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.

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 |

Location: | SCB-4017 |

Done