Recent progress on the Erdos-Hajnal Conjecture
Organizer
Benjamin Sudakov
Speaker
Alexander Scott
Time
Tuesday, April 30, 2024 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
A typical graph contains cliques and independent sets of no more than
logarithmic size. The Erdos-Hajnal Conjecture asserts that if we forbid
some induced subgraph H then we can do much better: the conjecture claims
that there is some c=c(H)>0 such that every H-free graph G contains a
clique or independent set of size at least |G|^c. The conjecture looks far
out of reach, and is only known for a small family of graphs. We will
discuss some recent progress.
Joint work with Tung Nguyen and Paul Seymour.
logarithmic size. The Erdos-Hajnal Conjecture asserts that if we forbid
some induced subgraph H then we can do much better: the conjecture claims
that there is some c=c(H)>0 such that every H-free graph G contains a
clique or independent set of size at least |G|^c. The conjecture looks far
out of reach, and is only known for a small family of graphs. We will
discuss some recent progress.
Joint work with Tung Nguyen and Paul Seymour.