Seminars & Colloquia Calendar
Recent progress on the Erdos-Hajnal Conjecture
Maria Chudnovsky (Princeton)
Location: zoom
Date & time: Wednesday, 03 March 2021 at 3:30PM - 4:30PM
Abstract: The Erdos-Hajnal conjecture states that for every graph H there is a constant epsilon(H) such that every n-vertex graph with no induced subgraph
isomorphic to H has a clique or a stable set of size n^{epsilon}. This conjecture has only been verified for a few graphs H, and in particular until recently it remained open for the case when H is a cycle of length 5. This special case received a considerable amount of attention. In this talk we will survey some known results, and discuss the recent proof for the case of a cycle of length 5.
This is joint work with Alex Scott, Paul Seymour and Sophie Spirkl.