One of the first applications of the probabilistic method is 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 any finite subsets A_1,...,A_r  \subset T, there exist A'_1 \subset A_1,..., A'_r \subset A_r, 

|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 the complexity and dichotomy for graph ordering problems.

Joint work with Jarik Nesetril.