User Tools

Site Tools


Speaker: Maria Chudnovsky (Princeton)

Title: Recent Progress on the Erdos--Hajnal Conjecture

Virtual Combinatorics Seminar, Tuesday, April 7, 2020

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 Erdos and Hajnal states 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. I will discuss the history of this problem and some recent theorems related to it.

seminars/comb/abstract.202004chu.txt · Last modified: 2020/05/17 22:30 by zaslav