The Erdős-Hajnal conjecture for the five-cycle

Speaker: 

Sophie Spirkl

Affiliation: 

University of Waterloo

Date: 

Wed, 03/03/2021 - 11:30am

Venue: 

Zoom meeting (see below)

Abstract: 

The Erdős-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 = C_5$ (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.

This is a seminar of the Combinatorial Mathematics Society of Australasia.

To attend email cmsa-webinar@monash.edu with the subject 'subscribe' to receive zoom details. [You only need to subscribe once, not for future talks.]

School Seminar Series: