MATH Seminar

Title: A few steps towards the Erdos–Hajnal conjecture
Seminar: Combinatorics
Speaker: Tung Nguyen of Princeton University
Contact: Liana Yepremyan, liana.yepremyan@emory.edu
Date: 2024-03-26 at 10:00AM
Venue: MSC W201
Download Flyer
Abstract: A cornerstone of Ramsey theory says that every graph contains a clique or independent set of logarithmic size, which is asymptotically optimal for almost all graphs. The Erd?s–Hajnal conjecture from 1977 predicts a very different situation in graphs with forbidden induced subgraphs; more precisely, the conjecture asserts that for every graph $H$, there exists $c=c(H)>0$ such that every $n$-vertex graph with no induced copy of $H$ has a clique or independent set of size at least $n^c$. This conjecture remains open, and we will discuss recent progress on it in the talk.