BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Peter Allen (LSE)
DTSTART:20200921T140000Z
DTEND:20200921T150000Z
DTSTAMP:20260423T052448Z
UID:EPC/24
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/EPC/24/">Wea
 k expansion and strong regularity</a>\nby Peter Allen (LSE) as part of Ext
 remal and probabilistic combinatorics webinar\n\n\nAbstract\nIn previous w
 ork\, embedding large graphs into subgraphs of random graphs is generally 
 done vertex by vertex\, using the Sparse Regularity Lemma\, looking only o
 ne step ahead\, and maintaining regularity properties throughout using a t
 echnical tool called inheritance of regularity. This approach cannot work 
 for very sparse random graphs\, even though it is believed that the embedd
 ing statements do remain true. We develop an alternative approach\, showin
 g that given a partial embedding and looking several steps ahead\, the set
  of extensions has a weak expansion property\; leveraging this one can per
 form vertex by vertex embedding without the need for inheritance of regula
 rity\, and as a result the approach works in sparser random graphs. In ord
 er to make this approach work\, we need to use a strengthened version of t
 he Sparse Regularity Lemma.\n\nI will outline the new approach briefly\, a
 nd explain how to use it to prove two new results.\n\n(i) For any  $\\gamm
 a>0$ and integers $r$\, $D$ and $\\Delta$\, there is $c>0$ such that if $p
 \\ge n^{-1/D+\\gamma}$ then $\\Gamma=G(n\,p)$ with high probability has th
 e following property. However $\\Gamma$ is $r$-coloured\, there is a colou
 r class which contains all $cn$-vertex graphs with degeneracy at most $D$ 
 and maximum degree at most $\\Delta$.\n\n(ii) If $p\\ge n^{-1+o(1)}$\, the
 n the random $k$-uniform hypergraph $\\Gamma=G^{(k)}(n\,p)$ with high prob
 ability has the following property. Every subgraph $G$ of $\\Gamma$ with m
 inimum codegree at least $(\\frac12+o(1))pn$ contains a tight Hamilton cyc
 le.\n\nBoth these results are asymptotically optimal. This is joint work w
 ith Julia Böttcher and with Olaf Parczyk and Vincent Pfenninger.\n
LOCATION:https://researchseminars.org/talk/EPC/24/
END:VEVENT
END:VCALENDAR