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} [χ(G_p)] \geq C_p \frac{χ(G)}{\log |V(G)|}$, and Bukh conjectured an improvement of $\mathbb{E}[χ(G_p)] \geq C_p \frac{χ(G)}{\log χ(G)}$. We prove a new spectral lower bound on $\mathbb{E}[χ(G_p)]$, as progress towards Bukh's conjecture. We also propose the stronger conjecture that for any fixed $p \leq 1/2$, among all graphs of fixed chromatic number, $\mathbb{E}[χ(G_p)]$ is minimized by the complete graph. We prove this stronger conjecture when $G$ is planar or $χ(G) < 4$. We also consider weaker lower bounds on $\mathbb{E}[χ(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