Tutte Colloquium - Sophie Spirkl

Title: Pure pairs

Abstract:

A pure pair in a graph G is a pair of subsets A and B of the vertex set such that between A and B, either all edges or no edges are present in G. This concept was first introduced in connected with the Erdos-Hajnal conjecture, but has since developed a life of its own. I will give an overview of results and open questions on pure pairs.

Based on joint work with Maria Chudnovsky, Jacob Fox, Alex Scott, and Paul Seymour.