Error message

  • Deprecated function: Optional parameter $js declared before required parameter $element is implicitly treated as a required parameter in include_once() (line 1445 of /var/www/html/mathtube.org/includes/bootstrap.inc).
  • Deprecated function: Optional parameter $input declared before required parameter $form_state is implicitly treated as a required parameter in include_once() (line 1445 of /var/www/html/mathtube.org/includes/bootstrap.inc).

The Erdos-Hajnal conjecture for the five-cycle

Speaker: Sophie Spirkl

Date: Thu, Jan 14, 2021

Location: Zoom, PIMS, University of Victoria

Conference: PIMS-UVic Discrete Math Seminar

Subject: Mathematics

Class: Scientific

Abstract:

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.