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.

arXiv comment8 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

References in corpus (3)

• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Fractional chromatic number of a random subgraph
• On Percolation and $NP$-Hardness

Cited by in corpus (1)

• On the chromatic number in the stochastic block model