权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Homogeneous structures, homomorphism-homogeneity, and automorphism groups

同构结构、同态同构和自同构群

基本信息

批准号：
EP/H00677X/1
负责人：
John Truss
金额：
$ 43.27万
依托单位：
University of Leeds
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2009
资助国家：
英国
起止时间：
2009 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FH00677X%2F1
关键词：
Homogeneous structures homomorphism homogeneity automorphism

项目摘要

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.

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