BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:David Correia (ETH Zurich) DTSTART:20210628T140000Z DTEND:20210628T150000Z DTSTAMP:20260423T035530Z UID:EPC/74 DESCRIPTION:Title: Tig ht bounds for powers of Hamilton cycles in tournaments\nby David Corre ia (ETH Zurich) as part of Extremal and probabilistic combinatorics webina r\n\n\nAbstract\nA basic result in graph theory says that any n-vertex tou rnament with in- and out-degrees at least n/4 contains a Hamilton cycle\, and this is essentially tight. In 1990\, Bollobás and Häggkvist signific antly extended this by showing that for any fixed k and ε >0\, and suffic iently large n\, all tournaments with degrees at least n/4+εn contain the k-th power of a Hamilton cycle. Given this\, it is natural to ask for a m ore accurate error term in the degree condition. We show that if the degre es are at least $n/4+cn^{1−1/⌈k/2⌉}$ for some constant c=c(k)\, then the tournament contains the k-th power of a Hamilton cycle. In particular \, in order to guarantee the square of a Hamilton cycle\, one only require s a constant additive term. We also present a construction which\, modulo a well-known conjecture on Turán numbers for complete bipartite graphs\, shows that the error term must be of order at least $n^{1−1/⌈(k−1)/2 ⌉}$\, which matches our upper bound for all even k. For odd k\, we belie ve that the lower bound can be improved and we show that for k=3\, there e xist tournaments with degrees $n/4+Ω(n^{1/5})$ and no cube of a Hamilton cycle. Additionally we also show that the Bollobás-Häggkvist theorem alr eady holds for $n=ε^{−Θ(k)}$\, which is best possible. This is joint w ork with Nemanja Draganic and Benny Sudakov.\n LOCATION:https://researchseminars.org/talk/EPC/74/ END:VEVENT END:VCALENDAR