BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201230T100000
DTEND;TZID=Asia/Seoul:20201230T110000
DTSTAMP:20260423T222519
CREATED:20201220T231608Z
LAST-MODIFIED:20240707T082035Z
UID:3389-1609322400-1609326000@dimag.ibs.re.kr
SUMMARY:Paul Seymour\, The Erdős-Hajnal conjecture is true for excluding a five-cycle
DESCRIPTION:In an n-vertex graph\, there must be a clique or stable set of size at least $C\log n$\, and there are graphs where this bound is attained. But if we look at graphs not containing a fixed graph H as an induced subgraph\, the largest clique or stable set is bigger. \nErdős and Hajnal conjectured in 1977 that for every graph H\, there exists c>0 such that every H-free graph has a clique or stable set of size at least $|G|^c$ (“H-free” means not containing H as an induced subgraph\, and |G| means the number of vertices of G). This is still open\, even for some five-vertex graphs H; and the case that has attracted most attention is when H is a cycle of length five. \nIt is true in that case. We will give a sketch of the proof\, which is via applying a lemma about bipartite graphs\, a variant of a theorem of I. Tomon. \nThis lemma has several other applications to the Erdős-Hajnal conjecture. For instance\, it implies that for every cycle C and forest T\, there exists c>0 such that every graph that is both C-free and T’-free (where T’ is the complement of T) has a clique or stable set of size $|G|^c$. (Until now this was open when C has length five and T is a 5-vertex path.) \nJoint work with Maria Chudnovsky\, Alex Scott and Sophie Spirkl.
URL:https://dimag.ibs.re.kr/event/2020-12-30/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR