## TAU Combinatorics Seminar 2022/23

When: Sunday, November 20, 10am
Where: 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ëte.

Joint work with O. Janzer and I. Tomon.