Small Subgraphs with Large Average Degree

In this paper we study the fundamental problem of finding small dense subgraphs in a given graph. For a real number \(s>2\) $s>2$ , we prove that every graph on n vertices with average degree \(d\ge s\) $d\ge s$ contains a subgraph of average degree at least s on at most \(nd^{-\frac{s}{s-2}}(\log d)^{O_s(1)}\) $n{d}^{-\frac{s}{s-2}}{(logd)}^{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 }\) $n^{1-\frac{2}{s}+\epsilon }$ contains a subgraph of average degree at least s on \(O_{\varepsilon ,s}(1)\) $O_{\epsilon ,s}(1)$ vertices, which is also optimal up to the constant hidden in the O(.) notation, and resolves a conjecture of Verstraëte.