Homogeneous structures, homomorphism-homogeneity, and automorphism groups

考虑一个图(一组顶点，一些顶点对由边连接)，或者一个有向图(其中边有方向)或推广(比方说其中顶点或边有几种可能的颜色)。对称性是几何学中熟悉的概念。图的对称性是“自同构”，对称量是由“自同构群”的丰富度来衡量的。通常，高度对称的物体是独一无二的，或者是规范的，或者是绝对的，在数学中非常自然地出现。这里我们考虑“齐次”结构(例如，图，有向图)，即可数无限的结构，使得任何有限部分同构扩展为自同构(非正式地，如果两个有限部分看起来相同，这被证明为全局对称性)。齐次结构的最初理论是作为模型理论(数学逻辑)的一部分而发展起来的。最重要的成就之一是Cherlin在1998年的一本专著中对齐次有向图进行了分类。这类例子很复杂，但描述干净而美观。然而，这个分类几乎没有阐明齐次(甚至是二元)结构通常是什么样子的，在导言中，Cherlin说他的分类“把我们带入了黑暗时代”。同质性的非常一般的框架意味着这个主题涉及到数学的许多部分，例如模型理论、有限模型理论与计算机科学的联系、群论、描述集合论，特别是组合学。这在很大程度上是在切尔林的回忆录之后发展起来的。例如，现在人们对齐次度量空间、组合学中的结构Ramsey理论以及拓扑动力学都有广泛的兴趣。重新审视同质结构中的分类已成为当务之急，以确定它可以合理地发挥多大作用，以及如果一个人需要不完全的分类，是否还有有意义的描述。这是当前项目的核心。我们将把这个分类与其他令人兴奋的最新发展联系起来。Ramsey理论和拓扑群中出现的共同主题告诉我们要研究有序的齐次结构。同构被同态取代的同质性的有趣概括开始出现。该项目将发展这些主题，也包括更传统的主题：自同构群的结构，较弱对称假设下的分类问题，以及与组合计数的联系(计算一个类中给定大小的对象的数量)。这门学科最近的一个主题是与约束满足的联系，这是计算机科学中的一个主题。对于给定的关系结构M(模板)，它自然引出了一个复杂性理论问题：对于输入的任何有限结构S，S到M是否存在同态？对于许多同质(或更广泛地说，欧米伽范畴)结构，这是一个自然而重要的计算问题。这导致了关于齐次结构的“约化”的一些新的和美丽的问题的提出。约束满足也促进了对“同态-同质”结构的研究。

Consider a graph (a set of vertices, with some pairs of vertices joined by edges), or a digraph (where edges have a direction) or generalizations (say where vertices or edges have several possible colours). Symmetry is a familiar notion from geometry. A symmetry of a graph is an `automorphism', and the amount of symmetry is measured by the richness of the `automorphism group'. Often, highly symmetrical objects are unique, or canonical, or categorical, and arise very naturally in mathematics. Here we consider `homogeneous' structures (e.g. graphs, digraphs), namely countably infinite structures such that any finite partial isomorphism extends to an automorphism (informally, if two finite parts look the same, this is witnessed by a global symmetry).The initial theory of homogeneous structures was developed as part of model theory (mathematical logic). One of the key achievements was a classification by Cherlin, in a monograph in 1998, of the homogeneous digraphs. The class of examples has great complexity but the description is clean and beautiful. However, the classification sheds little light on what homogeneous (even binary) structures look like in general, and in the introduction Cherlin says his classification `brings us into the dark ages'.The very general framework of homogeneity means that the subject touches many parts of mathematics, such as model theory, connections of finite model theory with computer science, group theory, descriptive set theory, and, in particular, combinatorics. Much of this has developed since Cherlin's memoir. For example, there is now wide interest in homogeneous metric spaces, in connections with structural Ramsey theory in combinatorics, and with topological dynamics. It has become urgent to revisit classification in homogeneous structures, to identify how far it can reasonably be taken, and whether, if one requires less than full classification, meaningful descriptions remain. This is at the heart of the current project.We shall relate this taxonomy to other exciting recent developments. Common themes arising in Ramsey theory and topological groups tell us to investigate ordered homogeneous structures. Intriguing generalizations of homogeneity, with isomorphisms replaced by homomorphisms, are starting to emerge. The project will develop these, and also more traditional themes: the structure of the automorphism groups, classification problems under weaker symmetry assumptions, and connections with combinatorial enumeration (counting the number of objects of given size in a class).A very recent theme in this subject is a connection with constraint satisfaction, a topic in computer science. It leads naturally to the complexity-theoretic question, given some relational structure M (a template): for input any finite structure S, is there a homomorphism from S to M? For many homogeneous (or more generally, omega-categorical) structures, this is a natural and important computational problem. This leads to the formulation of some new and beautiful questions about `reducts' of homogeneous structures. Constraint satisfaction also motivates the study of `homomorphism-homogeneous' structures.