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

Speaker: Gabor Kun (Renyi Inst, Budapest)

Thursday 22nd January, 3:00 in Fine Hall 224.

Title: The strong Erdos-Hajnal property and complexity dichotomy

One of the first applications of the probabilistic method was the construction 
of graphs with large girth and chromatic number. This works more generally for 
Constraint Satisfaction Problems over finite domains (for a fixed relational 
structure T, the problem CSP(T) asks if a given finite relational structure S 
has a homomorphism to T): the problem CSP(T) can be reduced to its restriction 
to relational structures with large girth. We extend this to the case when every 
relation of T has the strong Erdos-Hajnal Property (SEH), including, in 
particular, semialgebraic structures. (A relation R \subset T^r satisfies SEH 
if there exists delta>0 s.t. for all finite subsets A_1,...,A_r  \subset T, 
there exist A'_i \subset A_i with |A'_i| > \delta |A_i| for every i, s.t. 
A'_1 \times ... \times A'_r is either contained by R or they are disjoint.)

This enables us to settle a couple of conjectures on complexity and dichotomy 
for graph ordering problems.

Joint work with Jarik Nesetril.

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

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