Small subgraphs with large average degree

DOI10.1137/1.9781611977554.CH90arXiv2207.02170OpenAlexW4316652326MaRDI QIDQ6404075FDOQ6404075

Authors: Oliver Janzer, Benny Sudakov, István Tomon 

Publication date: 5 July 2022

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}^{-fracss-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-frac2s+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.

Full work available at URL: https://doi.org/10.1137/1.9781611977554.ch90

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

This page was built for publication: Small subgraphs with large average degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404075)