*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday 30th November, 3:00 in Fine Hall 224. Speaker: Sophie Spirkl (Princeton) Title: Sparse graphs and the Erdos-Hajnal conjecture A class C of graphs has the ``strong Erdos-Hajnal property'' if there is a constant c > 0 with the following property. In every graph in C, with n vertices say, there are two disjoint sets of vertices A and B with |A|,|B| > cn, and either every vertex in A is adjacent to every vertex in B, or there are no edges between A and B. Liebenau and Pilipczuk conjectured that for every tree T, the class of graphs containing neither T nor its complement as induced subgraphs has the strong Erdos-Hajnal property. I will talk about some progress towards this conjecture, and related results. Joint work with Anita Liebenau, Marcin Pilipczuk, and Paul Seymour. Next week: No seminar Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)