Event Type
Lectures
Thursday, January 30, 2020 4:30 PM
Professor Maria Chudnovsky (Princeton University)
Mathematics Research Center

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.