  In this paper we study 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^{-\frac{s}{s-2}}(\log d)^{O_s(1)}$ vertices.
This is optimal up to the polylogarithmic factor, and resolves a conjecture of
Feige and Wagner. In addition, we show that every graph with $n$ vertices and
average degree at least $n^{1-\frac{2}{s}+\varepsilon}$ contains a subgraph of
average degree at least $s$ on $O_{\varepsilon,s}(1)$ vertices, which is also
optimal up to the constant hidden in the $O(.)$ notation, and resolves a
conjecture of Verstra\"ete.
