***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Sophie Spirkl (Waterloo)
Thursday 11th February, 3:00 via Zoom.
The Zoom link and password will be mailed to the seminar mail list.
Title: The Erdos-Hajnal conjecture for graphs with no five-cycle
The Erdos-Hajnal conjecture states that for every graph H there exists
c > 0 such that every n-vertex graph G either contains H as an induced subgraph,
or has a clique or stable set of size at least n^c. I will talk about a proof of
this conjecture for the case H = C5 (a five-cycle), and related results. The
proof is based on an extension of a lemma about bipartite graphs due to Pach and
Tomon.
This is joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour.
----------------------------------
Next week: Michael Krivelevich
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)