***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Tung Nguyen (Princeton)

TUESDAY April 11, 3:00 in Fine Hall 224. (Note the unusual date!)

Title: The near-Erdős–Hajnal property of some prime graphs

Erdős and Hajnal conjectured that for every graph H, there exists 
c>0 such that every graph on n vertices with no induced copy of H 
contains a clique or a stable set of size at least n^c. Alon, Pach, 
and Solymosi reduced this conjecture to the case when H is prime, 
or equivalently when H cannot be obtained by blowing up smaller 
graphs. But so far, it has not been shown for any prime graph with 
more than five vertices. 

This talk describes a construction of infinitely many prime graphs 
that each "almost"  satisfies the Erdős–Hajnal conjecture. More 
exactly, for every such graph H, every graph on n vertices with no 
induced copy of H contains a clique or a stable set of size at least

                  2^{(log n)^{1-o(1)}}.

The proof method actually gives the stronger result that each such 
graph H has the "near-polynomial Rödl–Nikiforov" property, which 
will be explained in the talk.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)