Gábor Kun: The strong Erdős-Hajnal property and CSP dichotomy

Abstract: 

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, including, in particular, semialgebraic structures.

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

https://www.renyi.hu/~geza/GeoSzem/