Speaker: Alex Neal-Riasanovsky
Title: Partitioning random graphs with Turán graph
Abstract: In 1987, Bollobás showed that the chromatic number of a random graph $G(n,p)$ is asymptotically almost surely equal to $(1+o(1))\dfrac{n}{\log_b(n)}$ where $b = 1/(1-p)$. Essential to the proof was a sharp concentration of the clique number $\omega$ number of $G(n,p)$. Motivated by a problem of computing the edit distance function of a random graph, we prove a generalization where "clique" is replaced by induced copies of (the complement of) the $t$-partite Turán graph. This result matches a special case of a concentration result due to Bollobás and Thomason in 2000 where "clique" is instead replaced by any induced subgraph from a hereditary property.