Xavier Pérez-Giménez “The chromatic number of a random lift of K_d” | Big Seminar

December 10, 2020
19.00 MSK (UTC +3)

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.

The talk will be held in zoom
Meeting ID: 279-059-822
Password: first 6 decimal places of $\pi$ after the decimal point

You can also write to Alexander Polyanskii (alexander.polyanskii@yandex.ru) or to Maksim Zhukovskii (zhukmax@gmail.com) if you want to be added to mailing list.

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.

Watch the video:

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.