Sophie Spirkl, Princeton University

Abstract

Given a graph G, two subsets A and B of its vertex set are a "pure pair" if either all or none of the edges between them are present in G. 

Motivated by the Erdos-Hajnal conjecture, we ask: Given a class of graphs C defined by forbidding induced subgraphs, do all graphs in C have large pure pairs? More precisely, for which functions f and g does every n-vertex graph in C have a pure pair with |A| = f(n) and |B| = g(n)?  

Two years ago, I talked about classes of graphs for which f and g can be chosen as linear functions. This time, I will talk about more recent progress on the general question, and related results.  

Joint work with Maria Chudnovsky, Jacob Fox, Alex Scott, and Paul Seymour.