BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Small subgraphs with large average degree  - Oliver Janzer (Cambri
 dge)
DTSTART:20221010T133000Z
DTEND:20221010T143000Z
UID:TALK183995@talks.cam.ac.uk
CONTACT:103978
DESCRIPTION:We study the fundamental problem of finding small dense subgra
 phs 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 d
 egree at least s on O_{eps\,s}(1) vertices\, which is also optimal up to t
 he constant hidden in the O(.) notation\, and resolves a conjecture of Ver
 straete. Joint work with Benny Sudakov and Istvan Tomon. 
LOCATION:MR12
END:VEVENT
END:VCALENDAR