Two-Point Concentration of the Independence Number of the Random Graph
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 …