Special Seminar - Sophie Spirkl

Friday, January 26, 2018 9:30 am - 9:30 am EST (GMT -05:00)

Title: Sparse graphs with forbidden induced subgraphs and the Erdos-Hajnal conjecture

Speaker: Sophie Spirkl
Affiliation: Princeton University
Room: MC 5501


A graph G is called H-free if it does not contain H as an induced subgraph, i.e. H cannot be obtained from G by deleting vertices. A famous conjecture due to Erdos and Hajnal states that for every graph H, there is a constant c > 0 such that in every n-vertex H-free graph G, there is a set of nc vertices that are either all pairwise adjacent or all pairwise non-adjacent. This conjecture is open, although it has been proved for some graphs H.

I will give some background on this conjecture and discuss recent results (joint with Anita Liebenau, Marcin Pilipczuk, and Paul Seymour) on a variant this problem. The main tool for these results are sparse graphs, i.e. graphs in which no vertex is adjacent to more than small fraction of the vertices.