University of Cambridge > Talks.cam > Combinatorics Seminar > Small subgraphs with large average degree

Small subgraphs with large average degree

Add to your list(s) Download to your calendar using vCal

  • UserOliver Janzer (Cambridge)
  • ClockThursday 20 October 2022, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact ibl10.

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(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.

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2024 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity