Homogeneous structures, constraint satisfaction problems, and topological clones

克隆是泛代数中具有核心重要性的群的推广。在过去的15年里，它们成为研究约束满足问题(CSP)计算复杂性的重要工具。对于无限域上的CSP，我们必须研究无限域上的函数克隆；这些克隆自然具有逐点收敛的拓扑结构。这种拓扑使它们成为拓扑克隆，就像由置换群产生的拓扑群关于逐点收敛拓扑学一样。如果CSP的关系具有泛范畴一阶理论，则CSP的计算复杂性仅取决于这些关系的拓扑多态克隆。这包括在具有有限关系签名的齐次结构上一阶可定义的所有关系，并且对应的CSP类非常大，包含许多在理论计算机科学的各个领域中已经研究过的自然计算问题。研究这些关系的多态克隆的一个重要方法是Ramsey理论。这个项目的目标是研究拓扑克隆的拓扑和代数性质之间的相互作用，特别是对于与上述应用相关的问题，因为CSP的复杂性。我们还想进一步发展用于这些调查的拉姆齐方法。

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.