Xavier Pérez-Giménez "The chromatic number of a random lift of $K_d$"

Xavier Pérez-Giménez from University of Nebraska-Lincoln will give the talk "The chromatic number of a random lift of $K_d$" on the labs' Big Seminar.

Abstract:

An $n$-lift of a graph $G$ is a graph from which there is an $n$-to-$1$ covering map onto $G$. Amit, Linial, and Matoušek (2002) raised the question of whether the chromatic number of a random $n$-lift of $K_5$ is concentrated on a single value. We consider a more general problem, and show that for fixed $d\ge 3$ the chromatic number of a random lift of $K_d$ is (asymptotically almost surely) either $k$ or $k+1$, where $k$ is the smallest integer satisfying $d < 2k \log k$. Moreover, we show that, for roughly half of the values of $d$, the chromatic number is concentrated on $k$. The argument for the upper-bound on the chromatic number uses the small subgraph conditioning method, and it can be extended to random $n$-lifts of $G$, for any fixed $d$-regular graph $G$.

This is joint work with JD Nir.

Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.