Online seminar – June 2020 – Professor Maria Chudnovsky – Holes with hats and the Erdős-Hajnal Conjecture

Joy Lukman

  • Tuesday
    2 June 2020
    8:00 am - 9:00 am

Event Time:
Tuesday, 2 June @ 0800 (AEST) (Melbourne time)
Monday, 1 June @ 1800 (EDT) (New York, USA time)
Monday, 1 June @ 2300 (BST) (London time)



Presenter: Professor Maria Chudnovsky (Princeton University)

Biography: Princeton University & Wikipedia

Topic: Holes with hats and the Erdős-Hajnal Conjecture

Abstract: The Erdős-Hajnal conjecture states that for every graph H there is a constant epsilon(H) such that every n-vertex graph with no induced subgraph isomorphic to H has a clique or a stable set of size n^{epsilon}. This conjecture has only been verified for a few graphs H, and in particular it is open for the case when H is a “house”: the complement of the five vertex path.

A “hole with a hat” is a graph consisting of a cycle of length at least 4, together with an additional vertex that has exactly two neighbors in the cycle, and these two neighbors are adjacent to each other. Thus the house is the smallest example of a hole with a hat.

We prove that the conclusion of the Erdős-Hajnal Conjecture holds if all holes with a hat are excluded. The proof uses several techniques, including a new notion of “almost non-crossing separations”.

This is joint work with Paul Seymour.

Structure: 45 minutes seminar with 15 minutes question time

Seminar Recording & Slides:

Please click here for the recording of the webinar.

Please click here for the presentation slides.