BIMSA > Research seminar in Discrete Mathematics Recent progress on the Erdos-Hajnal Conjecture
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.