Expected Chromatic Number of Random Subgraphs

Abstract

Given a graph $G$ and $p\in [0,1]$, let $G_p$ denote the random subgraph of $G$ obtained by keeping each edge independently with probability $p$. Alon, Krivelevich, and Sudokov proved $\mathbb{E}[\chi (G_p)]\ge C_p\frac{\chi (G)}{\log |V(G)|}$, and Bukh conjectured an improvement of $\mathbb{E}[\chi (G_p)]\ge C_p\frac{\chi (G)}{\log \chi (G)}$. We prove a new spectral lower bound on $\mathbb{E}[\chi (G_p)]$, as progress towards Bukh's conjecture. We also propose the stronger conjecture that for any fixed $p\le 1/2$, among all graphs of fixed chromatic number, $\mathbb{E}[\chi (G_p)]$ is minimized by the complete graph. We prove this stronger conjecture when $G$ is planar or $\chi (G)<4$. We also consider weaker lower bounds on $\mathbb{E}[\chi (G_p)]$ proposed in a recent paper by Shinkar; we answer two open questions of Shinkar negatively and propose a possible refinement of one of them.

8 pages plus an appendix (14 total). Multiple figures, one of which before the appendix. Work done as part of the 2018 program of the Summer Undergraduate Math Research at Yale