On the Existence of Polynomially Large Cliques or Stable Sets in H-free Graphs

Abstract

Given a graph H, we say that H has the Erdos-Hajnal property if there exists a constant τ > 0 such that every H-free graph G contains a clique or a stable set of size at least |G| τ . The question of whether or not all graphs have this property has remained unsolved for over thirty years, and there has been a rapidly expanding body of literature on the subject (see, e.g., [1], [7], [8], [18], [28], [37]). Recently, Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl [13] verified the Erd˝os-Hajnal conjecture for H = C5, which has been regarded as case of particular interest by many (see, e.g., [2]). This thesis will be detailing the most recent results about this conjecture as well as its potential directions moving forward.