BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Small subgraphs with large average degree  - Olive
 r Janzer (Cambridge)
DTSTART;TZID=Europe/London:20221020T143000
DTEND;TZID=Europe/London:20221020T153000
UID:TALK183998AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/183998
DESCRIPTION:We study the fundamental problem of finding small 
 dense subgraphs in a given graph. For a real numbe
 r s>2\, we prove that every graph on n vertices wi
 th average degree at least d contains a subgraph o
 f 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 conje
 cture of Feige and Wagner. In addition\, we show t
 hat every graph with n vertices and average degree
  at least n^{1-2/s+eps} contains a subgraph of ave
 rage degree at least s on O_{eps\,s}(1) vertices\,
  which is also optimal up to the constant hidden i
 n the O(.) notation\, and resolves a conjecture of
  Verstraete. Joint work with Benny Sudakov and Ist
 van Tomon. 
LOCATION:MR12
CONTACT:
END:VEVENT
END:VCALENDAR