### The chromatic number of a random lift of K_d

- Series
- Combinatorics Seminar
- Time
- Friday, September 11, 2020 - 15:00 for 1 hour (actually 50 minutes)
- Location
- https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
- Speaker
- Xavier Pérez Giménez – University of Nebraska-Lincoln

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 Matousek (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 ≥ 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.)