The Erdos-Hajnal Conjecture

Krysztof Choromanski

Columbia University

Abstract

The celebrated Erdos-Hajnal Conjecture says that for every undirected graph H there exists \epsilon(H)>0 such that every undirected graph G that does not contain H as an induced subgraph contains either a clique or a stable set of size at least |G|^{\epsilon(H)}. In its directed version (equivalent to the undirected one) undirected graphs are replaced by tournaments and cliques and stable sets by transitive subtournaments. The Conjecture is still open in the most general scenario.

For a long time it was known only for a few small graphs. Some time ago Alon, Pach and Solymosi proposed a procedure that enables to obtain bigger graphs satsfying the Conjecture from the smaller ones that satisfy it. Recently Berger, Choromanski and Chudnovsky managed to prove the Conjecture for a new infinite family of tournaments that cannot be obtained in such a way (so-called galaxies). As a corollary they got that among all