Two-Point Concentration of the Independence Number of the Random Graph

Abstract

We show that the independence number of $G_{n,p}$ is concentrated on two values if $n^{-2/3+\epsilon }<p\le 1$. This result is roughly best possible as an argument of Sah and Sawhney shows that the independence number is not, in general, concentrated on 2 values for $p=o\left((\log (n)/n{)}^{2/3}\right)$. The extent of concentration of the independence number of $G_{n,p}$ for $\omega (1/n)<p\le n^{-2/3}$ remains an interesting open question.