기초과학연구원 이산수학그룹
On May 16, 2023, Oliver Janzer from the University of Cambridge gave a talk at the Discrete Math Seminar on finding a subgraph of large average degree on a small vertex set at the Discrete Math Seminar. The title of his talk was “small subgraphs with large average degree.”
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ëte.
Joint work with Benny Sudakov and Istvan Tomon.