Copenhagen-Jerusalem Combinatorics Seminar- Oliver Janzer (Trinity College, Cambridge): "Small subgraphs with large average degree"

Date: 
Thu, 19/01/202317:15-19:00
Location: 
Zoom
Zoom Link: https://ucph-ku.zoom.us/j/69937085835


Password: 123456

Title:  Small subgraphs with large average degree

Abstract:

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^{-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-2/s+eps} contains a subgraph of average degree at least s on O_{eps,s}(1) vertices, which is also optimal up to the constant hidden in the O(.) notation, and resolves a conjecture of Verstraete.

Joint work with Benny Sudakov and Istvan Tomon.