Sophie Spirkl, 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.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail:, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.