Relational Structures and Applications

关系结构和应用

• 批准号: RGPGP-2014-00062
• 负责人: Laflamme, Claude
• 金额: $ 0.8万
• 依托单位: University of Calgary
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Group
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=635503
• 关键词: Relational; Structures; Applications

This research program aims at further understanding the connections between the Fraissé theory of amalgamation classes and homogeneous structures, Ramsey theory, and topological dynamics of automorphism groups, driven toward new applications. We propose to formally join our efforts as a team as part of this program, in particular proposing the following lines of research:Precompact expansionsThe objective is to determine an optimal expansion of homogeneous structures to obtain a Ramsey class with the expansion property, thus providing the existence and means to describe the universal minimal flows. The approach here is to capture basic structural properties with the help of a minimal number of well chosen predicates, very much related to the work on canonical partitions well known by this team. Oscillation stability The famous distortion problem asked whether the Hilbert sphere is approximately indivisible. The notion of oscillation stability was introduced for topological groups, and it turns out that these concepts are equivalent for homogeneous metric spaces. Several results followed, including the proof of a general result that yields the oscillation stability of the Urysohn sphere. This is a very rich area very much influenced by problems in analysis, but with some unresolved fundamental questions.Overgroups of automorphism groupsWe have explored various natural overgroups of the automorphism group of the Rado graph, generalizing well known methods for reducts. The surprising results in this work point to further work investigating the corresponding overgroups of the other well known homogeneous structures, work very much related to the study of the hypergraph of copies of countable homogeneous structures providing insight into which maps generalizing graph homeomorphisms preserve the copies.Constraint RecognitionThere are recent connections involving homogeneous structures, omega-categoricity and constraint satisfaction with applications to complexity problems. We propose to investigate some very natural questions general to the study of reducts of omega-categorical structures and the themes above.Distinguishing numberThis curious notion is a rough measure of symmetry, and we have conjectured that primitive structures should have a distinguishing number of either 2 or omega. This work appears very much related to similar conjectures within the realm of infinite permutation groups, and we propose to extend the investigation of this parameter for homogeneous structures. EquimorphyThis fundamental notion explores conditions when two relational structures embed in the other, arising naturally when one studies the preorder of embeddability on relational structures of a fixed age. The failure of the Cantor-Bernstein theorem for sets in the context of embeddings is key to results that are applied in the study of linear orders, graphs and tournaments. We are using these tools from the study of relational structures, such as the notion of chainability and kernel to make advances in this area which has to date largely been studied only for graphs and trees.C-XY homogeneous structuresThese generalize the classical homogeneity notion. The classification of the C-HH structures was recently done by D. Lockett, and a team’s NSERC USRA has made substantial progress in the finite C-MH case, providing renewed hope for the complete classification of this class in the countable case. Intervals in relational structuresWe have developed techniques, including the notion of inclusive intervals, interval decomposition and lexicographic products, toward understanding primitive structures and cop-win graphs. We will further investigate notions of critical primitivity in the infinite context.

本研究计划旨在进一步了解合并类和齐次结构，拉姆齐理论和自同构群的拓扑动力学的弗雷斯理论之间的联系，朝着新的应用驱动。我们建议正式加入我们的努力，作为这个计划的一部分，特别是提出以下研究路线：预紧扩展目标是确定均匀结构的最佳扩展，以获得具有扩展属性的Ramsey类，从而提供存在性和描述通用最小流的方法。这里的方法是在最少数量的精心选择的谓词的帮助下捕获基本的结构属性，这与这个团队所熟知的规范划分的工作非常相关。振荡稳定性著名的畸变问题是关于希尔伯特球面是否近似不可分的问题。在拓扑群中引入了振荡稳定性的概念，证明了这些概念在齐次度量空间中是等价的。随后的几个结果，包括证明的一般结果，产生振荡稳定的Urysohn球。这是一个非常丰富的领域非常影响问题的分析，但有一些悬而未决的基本问题。自同构群的扩群我们已经探讨了各种自然扩群的自同构群的Rado图，推广众所周知的方法约简。这项工作中令人惊讶的结果指向进一步的工作调查相应的其他众所周知的同质结构的扩群，工作非常相关的研究的超图的副本可数同质结构提供洞察到哪些地图推广图同胚保持副本。Omega-范畴性和约束满足与复杂性问题的应用。我们建议调查一些非常自然的问题一般的研究约简的欧米茄范畴结构和themes. Distinguishingnumber这个奇怪的概念是一个粗略的措施对称性，我们已经证明，原始结构应该有一个区别的号码2或欧米茄。这项工作似乎非常相关的领域内的无限置换群的类似acetrutures，我们建议扩大这一参数的均匀结构的调查。Equimorphy这个基本概念探讨了两个关系结构嵌入另一个关系结构的条件，当人们研究固定年龄的关系结构的嵌入性前序时，自然会出现这种情况。Cantor-Bernstein定理在嵌入背景下的失败是应用于线性序、图和竞赛图研究结果的关键。我们正在使用这些工具，从关系结构的研究，如概念的chainability和内核取得进展，在这一领域，迄今为止，主要是研究图和trees.C-XY齐次structureThese推广了经典的同质性概念。最近D. Lockett和一个团队的NSERC USRA在有限C-MH情况下取得了实质性进展，为可数情况下该类的完整分类提供了新的希望。关系结构中的区间我们已经开发了一些技术，包括包含区间的概念，区间分解和字典积，以理解原始结构和cop-win图。我们将进一步研究无限语境中的临界连续性概念。