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 two values for $ p = o ( (\log (n)/n)^{2/3} )$ . 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.

Keywords

• 05c80
• 60c05