Stanford University

Recent progress on the Erdős-Hajnal conjecture

Thursday, January 30, 2020 4:30 PM
Professor Maria Chudnovsky (Princeton University)

What is the effect of excluding an induced subgraph on the global structure of a graph?  While there do not seem to be general structural consequences, a conjecture of Erdős and Hajnal says that graphs with forbidden induced subgraphs behave very differently from general graphs; more
precisely, they contain much larger cliques or stable sets.  This conjecture is still open.  In this talk we will discuss the history of this problem and some recent theorems related to it.