Reconstructing the topology on polymorphism clones of the rationals and its application to CSP's
- Date: Wednesday 27 June 2018, 16:00 – 17:00
- Location: EC Stoner SR (7.70)
- Type: Logic, Seminars, Pure Mathematics
- Cost: Free
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.