Homogeneous structures, homomorphism-homogeneity, and automorphism groups

点击翻译按钮获取中文摘要

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.