BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Oliver Janzer (Trinity College\, Cambridge)
DTSTART:20230119T151500Z
DTEND:20230119T170000Z
DTSTAMP:20260422T065640Z
UID:CJCS/103
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/CJCS/103/">S
 mall subgraphs with large average degree</a>\nby Oliver Janzer (Trinity Co
 llege\, Cambridge) as part of Copenhagen-Jerusalem Combinatorics Seminar\n
 \n\nAbstract\nWe study the fundamental problem of finding small dense subg
 raphs 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 averag
 e degree at least s on at most nd^{-s/(s-2)}(log d)^{O_s(1)} vertices. Thi
 s is optimal up to the polylogarithmic factor\, and resolves a conjecture 
 of Feige and Wagner. In addition\, we show that every graph with n vertice
 s 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 V
 erstraete.\n\nJoint work with Benny Sudakov and Istvan Tomon.\n
LOCATION:https://researchseminars.org/talk/CJCS/103/
END:VEVENT
END:VCALENDAR