On the jump of the clique chromatic number for binomial random graphs

Combinatorics Seminar
Friday, March 12, 2021 - 4:00pm for 1 hour (actually 50 minutes)
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Dieter Mitsche – Institut Camille Jordan, Univ. de Lyon – http://math.univ-lyon1.fr/~mitsche/
Lutz Warnke

Given a graph G, the clique chromatic number of G is the smallest number of colors needed to color the vertices of G so that no maximal clique containing at least two vertices is monochromatic.
We solve an open question proposed by McDiarmid, the speaker, and Pralat concerning the asymptotic order of the clique chromatic number for binomial random graphs.
More precisely, we find the correct order of the clique chromatic number for most values of the edge-probability p around n^{-1/2}. Furthermore, the gap between upper and lower bounds is at most a logarithmic factor in n in all cases.

Based on joint work in progress with Lyuben Lichev and Lutz Warnke.

(Please note the unusual time from 4-5pm, due to the Virtual Admitted Student Day in the School of Mathematics.)