Small subgraphs with large average degree

Abstract

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 $n{d}^{-\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}+\epsilon }$ contains a subgraph of average degree at least $s$ on $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.

11 pages