Talk information

Date: Sunday, November 20, 2022
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Benny Sudakov (ETH Zurich)
Title: Small subgraphs with large average degree

Abstract:

In this talk we discuss 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^{-s/(s-2)} \mathrm{polylog} d$ vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. Our methods can also show every graph with $n$ vertices and average degree at least $n^{1-2/s+\epsilon}$ contains a subgraph of average degree at least $s$ on $O(1)$ vertices, which is tight and resolves a conjecture of Verstra"ete.

Joint work with O. Janzer and I. Tomon.