Trees and Linear Anticomplete Sets

Start Date: September 10, 2018
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:
For which graphs H is it true that there is an epsilon > 0 such that for all n > 1, and for every n-vertex graph G that does not contain H as an induced subgraph, either G has a vertex of degree at least epsilon n, or G contains two disjoint vertex sets A, B with |A|, |B| >= epsilon n, and there is no edge between A and B in G? Liebenau and Pilipczuk conjectured that this is true if H is a forest. I will talk about a proof of this conjecture, connections to the Erdos-Hajnal conjecture, and related questions. Joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour.

Events