기초과학연구원 이산수학그룹
On April 1, 2021, Sophie Spirkl from the University of Waterloo gave an online talk on pure pairs in an ordered graph at the Virtual Discrete Math Colloquium. The title of her talk was “Pure pairs in ordered graphs“.
A pure pair in a graph G is a pair of subsets A, B of the vertex set of G such that in G, either all of the edges or none of the edges between A and B are present. Pure pairs have been studied recently motivated by their connections to the Erdos-Hajnal conjecture.
In this talk, I will discuss the topic of pure pairs in ordered graphs, that is, graphs with a linear ordering on their vertex set. If we exclude a graph H as an ordered induced subgraph, how large a pure pair can we guarantee? I will talk about how the answer differs from the case of unordered graphs and show some of the techniques used.
Based on joint work with Maria Chudnovsky, Jacob Fox, Alex Scott, and Paul Seymour.