Title: Sparse graphs with forbidden induced subgraphs and the Erdos-Hajnal conjecture
| Speaker: | Sophie Spirkl |
| Affiliation: | Princeton University |
| Room: | MC 5501 |
Abstract:
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.