***********************************
* 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)