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 s>2, we prove that every graph on n vertices with average degree d s d≥s contains a subgraph of average degree at least s on at most nd^-s{s-2} (d) ^Oₛ (1) nd-ss-2 (logd) Os (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-2{s+ } n1-2s+ε contains a subgraph of average degree at least s on O, ₒ (1) Oε, s (1) vertices, which is also optimal up to the constant hidden in the O (. ) notation, and resolves a conjecture of Verstraëte.