Download as iCal file


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.