Dense Subgraphs in Random Graphs

Abstract

For a constant $\gamma \in [0,1]$ and a graph $G$, let ${\omega }_{\gamma }(G)$ be the largest integer $k$ for which there exists a $k$-vertex subgraph of $G$ with at least $\gamma \left(\genfrac{}{}{0ex}{}{k}{2}\right)$ edges. We show that if $0<p<\gamma <1$ then ${\omega }_{\gamma }(G_{n,p})$ is concentrated on a set of two integers. More precisely, with $\alpha (\gamma ,p)=\gamma \log \frac{\gamma }{p}+(1-\gamma )\log \frac{1-\gamma }{1-p}$, we show that ${\omega }_{\gamma }(G_{n,p})$ is one of the two integers closest to $\frac{2}{\alpha (\gamma ,p)}(\log n-\log \log n+\log \frac{e\alpha (\gamma ,p)}{2})+\frac{1}{2}$, with high probability. While this situation parallels that of cliques in random graphs, a new technique is required to handle the more complicated ways in which these "quasi-cliques" may overlap.