Seminar Details
Pure Pairs in Graphs with Forbidden Induced Subgraphs
- Start Date: March 2, 2020
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Sophie Spirkl - Princeton University
- Event Location: Hill Center-Room 705
- Presentation Type: Stand Alone Presentation
- 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.