Reconstructing the topology on polymorphism clones of the rationals and its application to CSP's

Edith Vargas García, Instituto Tecnológico Autónomo de México (ITAM). Part of the Logic Seminar Series.

A 'Constraint Satisfaction Problem' (CSP) of a finite relational structure B, denoted by CSP(B), can be expressed as the problem of deciding whether there exists a homomorphism phi from a finite relational structure A to B.

'Clones' on a fixed set carry a natural topology, induced by the topology of pointwise convergence.  The polymorphism clones Pol(A) of a relational structure A are viewed abstractly as clones and as topological clones, their topology is the natural one.  'Automatic homeomorphicity' means that every isomorphism between two clones is a homeomorphism with respect to their pointwise convergence topologies.

In this talk we show that the polymorphism clone Pol(Q,<), with the strict relation < on the rationals Q, has automatic homeomorphicity with respect to the class of omega-categorical structures, without algebraicity.  Moreover, we will see how our result has a consequence in the computational complexity of the CSP(Q,<).

This work is joint with Mike Behrisch and John K. Truss.