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

Speaker: Alex Scott (Oxford)

Thursday 16th November, 3:00 in Fine Hall 224.

Title: VC-dimension and Erdős-Hajnal

A class of graphs has the Erdős-Hajnal property if there is some c>0
such that every graph G in the class has a clique or stable set of
size at least |G|^c.  Fox, Pach and Suk showed a few years ago that,
for every d, the class of graphs with VC-dimension at most d has
the "near Erdős-Hajnal property": namely, that there are cliques or
stable sets of size exp((log |G|)^{1-o(1)}).  We will show that in
fact these classes do have the full Erdős-Hajnal property.  Joint
work with Tung Nguyen and Paul Seymour.

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


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