A note on Two-Point Concentration of the Independence Number of $G_{n,m}$

Abstract

We show that the independence number of $G_{n,m}$ is concentrated on two values for $n^{5/4+\epsilon }<m\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)$. This result establishes a distinction between $G_{n,m}$ and $G_{n,p}$ with $p=m/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ in the regime $n^{5/4+\epsilon }<m<n^{4/3}$. In this regime the independence number of $G_{n,m}$ is concentrated on two values while the independence number of $G_{n,p}$ is not; indeed, for $p$ in this regime variations in $\alpha (G_{n,p})$ are determined by variations in the number of edges in $G_{n,p}$.

53 pages, 1 figure