The Erdös-Hajnal property for stable graphs.

Dario Garcia Rico (Leeds)

Frank Adams 1,

We say that a class C of finite graphs has the Erdös-Hajnal property if there is a constant d (depending only on the class C) such that every graph G in C, admits either a clique or an anticlique of size \( |G|^d \) .  It was conjectured by P. Erdös and A. Hajnal that for every graph H, the class of H-free graphs has the Erdös-Hajnal property.

Even if this conjecture still remains open, the Erdös-Hajnal property has been proved for several classes of finite graphs. For instance, the Erdös-Hajnal property was proved for families of finite (hyper-)graphs without the m-order property by M. Malliaris and S. Shelah, as an application of their Regularity Lemma for stable graphs

In this talk I will give a brief overview of the Erdös-Hajnal conjecture, and present a proof (due to A. Chernikov and S. Starchenko) of the Erdös-Hajnal property for stable graphs using ultraproducts, pseudofinite dimensions and basic properties of stable formulas.

Import this event to your Outlook calendar
▲ Up to the top