Homogeneous structures, constraint satisfaction problems, and topological clones

• Applicant: Professor Dr. Manuel Bodirsky
• Subject Area: Mathematics ; Theoretical Computer Science
• Term: from 2015 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 280296726

Clones are a generalisation of groups that are of central importance in universal algebra. In the last 15 years they became an important tool for studying the computational complexity of constraint satisfaction problems (CSPs). For CSPs on infinite domains, we have to study function clones on infinite domains; those are naturally equipped with the topology of pointwise convergence. This topology makes them to topological clones, in the same way as the topological groups that arise from permutation groups with respect to the pointwise convergence topolgy. If the relations of a CSP have an omega-categorical first-order theory, then the computational complexity of the CSP only depends on the topological polymorphism clone of those relations. This includes all relations that are first-order definable over homogeneous structures with finite relational signature, and the corresponding class of CSPs is very large and contains many natural computational problems that have been studied in various areas of theoretical computer science. An important method to study polymorphism clones of those relations is Ramsey theory. The goal of this project is to investigate the interplay of topological and algebraical properties of topological clones, in particular for the questions that are of relevance for the mentioned application for the complexity of CSPs. We also want to further develop the Ramsey methods for these investigations.

• DFG Programme: Research Grants