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.)
Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.
The ACO Seminar (2019–2020)