In this talk we discuss the fundamental problem of finding small dense subgraphs in a given graph. For a real number $s>2$, we prove that every graph on $n$ vertices with average degree at least $d$ contains a subgraph of average degree at least $s$ on at most $nd^{-s/(s-2)} \mathrm{polylog} d$ vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. Our methods can also show every graph with $n$ vertices and average degree at least $n^{1-2/s+\epsilon}$ contains a subgraph of average degree at least $s$ on $O(1)$ vertices, which is tight and resolves a conjecture of Verstraëte.
Joint work with O. Janzer and I. Tomon.