Small subgraphs with large average degree

Oliver Janzer (Trinity College, Cambridge)

19-Jan-2023, 15:15-17:00 (14 months ago)

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.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic


Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456

Organizers: Karim Adiprasito, Arina Voorhaar*
*contact for this listing

Export talk to