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


Date: Thursday February 9, 2.15 in Fine Hall 224
 
Speaker: Krzysztof Choromanski (Columbia)

Title:  New classes of tournaments satisfying the Erdos-Hajnal conjecture.

The Erdos-Hajnal conjecture states that for every graph H there exists
a constant c>0 such that every graph G that does not contain H as 
an induced subgraph contains a clique or a stable set of size at least
 |G|^c. The conjecture is still open. However some time ago a version 
for tournaments was proven to be equivalent to the original. In the 
tournament version, graphs are replaced by tournaments, and cliques and 
stable sets by transitive subtournaments. Both the tournament and the graph
versions of the conjecture are known to be true for some small graphs 
(or tournaments) H, and there are operations that build bigger graphs 
(or tournaments) for which the conjecture holds. I will show the conjecture 
for an infinite class of tournaments that is not obtained in the way 
described above. To the best of our knowledge, this is the first result of 
this kind.

The only five-vertex tournament for which the conjecture was open was
the tournament C_5 in which every vertex has outdegree two. I will show a 
proof that C_5 satisfies the conjecture. Consequently all 5-vertex 
tournaments satisfy the conjecture.

Finally I will talk about the tournaments that satisfy the conjecture in an
"almost linear sense" (so-called pseudocelebrities). A construction of all
pseudocelebrities will be given.

The part of the talk about pseudocelebrities is joint work with Maria
Chudnovsky and Paul Seymour. The other part is joint work with Eli Berger and
Maria Chudnovsky.
                       -----------

Next week: Bill Cook

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