Seminars & Colloquia Calendar
Pure pairs in graphs with forbidden induced subgraphs
Sophie Spirkl (Princeton University)
Location: Hill 705
Date & time: Monday, 02 March 2020 at 2:00PM - 3:00PM
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.