PIMS-UVic Discrete Math Seminar: Sophie Spirkl

  • Date: 01/14/2021
  • Time: 10:00
Lecturer(s):
Sophie Spirkl, UWaterloo
Location: 

Online

Topic: 

The Erdos-Hajnal conjecture for the five-cycle

Description: 

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.

Other Information: 

This event took place via zoom and a recording is available on mathtube.org.