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


Date: Thursday 15th October, 3:00 in Fine Hall 224.
 
Speaker: Aurelie Lagoutte (Lyon and Princeton)

Title: Clique-stable set separation


Consider the following communication complexity problem: Alice is given a 
clique K, Bob is given a stable set S, and they have to decide via a 
non-deterministic protocol whether K intersects S or not. A ``certificate'' 
for the non-intersection is a bipartition of the vertices such that K is
included in one side, and S is included in the other side.  A ``clique-stable 
set separator'' is a set of certificates which contains at least one 
certificate for each input (K,S). Given a class of graphs, the goal is to 
know whether there exists, for every graph of the class, a clique-stable set 
separator with only polynomially many certificates.

This question, originally restricted to the case of perfect graphs, occurred 
to Yannakakis when studying extended formulations of the stable set polytope 
(a polytope P has a small extended formulation if it is the projection of a 
polytope Q lying in a higher dimensional space, with a small number of facets). 
A recent result by Goos provides a super-polynomial lower bound for the 
class of all graphs, but the case of perfect graphs is still open.

We use different techniques to prove that a polynomial clique-stable set 
separator exists in restricted classes of graphs: probabilistic arguments 
for random graphs, VC-dimension for graphs where a split graph H is forbidden, 
the Strong Erdos-Hajnal property for graphs with no induced path on k vertices 
and its complement, and decomposition by 2-joins for perfect graphs with no 
balanced skew partition.

                       -----------

Next week: Hao Huang

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