Main content start

Recent progress on the Erdős-Hajnal conjecture

Speaker
Professor Maria Chudnovsky (Princeton University)
Date
Thu January 30th 2020, 4:30pm
Event Sponsor
Mathematics Research Center
Location
Building 380, Room 380W

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.