Dense Subgraphs in Random Graphs

Paul Balister, Béla Bollobás, Julian Sahasrabudhe +1

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…