Maria Chudnovsky 2 June 2020

Topic: Holes with hats and the Erdős-Hajnal Conjecture

Abstract: The Erdős-Hajnal conjecture states that for every graph H there is a constant epsilon(H) such that every n-vertex graph with no induced subgraph isomorphic to H has a clique or a stable set of size n^{epsilon}. This conjecture has only been verified for a few graphs H, and in particular it is open for the case when H is a “house”: the complement of the five vertex path.

A “hole with a hat” is a graph consisting of a cycle of length at least 4, together with an additional vertex that has exactly two neighbors in the cycle, and these two neighbors are adjacent to each other. Thus the house is the smallest example of a hole with a hat.

We prove that the conclusion of the Erdős-Hajnal Conjecture holds if all holes with a hat are excluded. The proof uses several techniques, including a new notion of “almost non-crossing separations”.

This is joint work with Paul Seymour.