BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Hong Liu (University of Warwick)
DTSTART:20210114T070000Z
DTEND:20210114T080000Z
DTSTAMP:20260423T021019Z
UID:SCMSComb/29
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/SCMSComb/29/
 ">A solution to Erdős and Hajnal’s odd cycle problem</a>\nby Hong Liu (
 University of Warwick) as part of SCMS Combinatorics Seminar\n\n\nAbstract
 \nIn 1981\, Erdős and Hajnal asked whether the sum of the reciprocals of 
 the odd cycle lengths in a graph with infinite chromatic number is necessa
 rily infinite. Let C(G) be the set of cycle lengths in a graph G and let C
 _odd(G) be the set of odd numbers in C(G). We prove that\, if G has chroma
 tic number k\, then ∑_{ℓ∈C_odd(G)} 1/ℓ≥(1/2−o_k(1))log k. This
  solves Erdős and Hajnal’s odd cycle problem\, and\, furthermore\, this
  bound is asymptotically optimal.\n\nIn 1984\, Erdős asked whether there 
 is some d such that each graph with chromatic number at least d (or perhap
 s even only average degree at least d) has a cycle whose length is a power
  of 2. We show that an average degree condition is sufficient for this pro
 blem\, solving it with methods that apply to a wide range of sequences in 
 addition to the powers of 2.\n\nFinally\, we use our methods to show that\
 , for every k\, there is some d so that every graph with average degree at
  least d has a subdivision of the complete graph K_k in which each edge is
  subdivided the same number of times. This confirms a conjecture of Thomas
 sen from 1984.\nJoint work with Richard Montgomery.\n\npw 061801\n
LOCATION:https://researchseminars.org/talk/SCMSComb/29/
END:VEVENT
END:VCALENDAR