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

Maria is a professor of mathematics at Princeton University.  Maria’s contributions to graph theory include the proof of the strong perfect graph theorem (with Neil Robertson, Paul Seymour, and Robin Thomas) characterizing perfect graphs as being exactly the graphs with no odd induced cycles of length at least 5 or their complements.

Other research contributions include co-authorship of the first polynomial time algorithm for recognizing perfect graphs and of a structural characterization of the claw-free graphs.

(Source: 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.