CAREER: Model Theory and Homogeneous Structures

职业：模型理论和齐次结构

• 批准号: 1848562
• 负责人: Thomas Scanlon
• 金额: $ 40万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2026-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1848562&HistoricalAwards=false
• 关键词: CAREER; Model; Theory; Homogeneous; Structures

Model theory is a branch of mathematical logic that studies combinatorial properties of mathematical structures (that is, sets equipped with certain operations). Since most mathematical objects can be represented as a structure, its subject matter is very broad and it interacts with several areas of mathematics. However, whereas other fields of mathematics are interested in specific structures, or classes of structures (for instance arithmetic studies the structure of the integers with addition and multiplication), model theory takes a step back and studies structures in general, looking for dividing lines and common properties. It singles out large classes of structures defined by combinatorial tameness conditions (which imply that the structure is in some sense not too complicated) and then attempts to understand the structures in those classes. One such class is that of NIP structures, which can be thought of as structures that have a geometric flavor. This class has received a lot of attention in the past decade. Another class is that of homogeneous structures, which are structures that have a lot of symmetries. Those are objects that belong to combinatorics and have been largely studied outside, or at the border of model theory. The main goal of this project is the investigation of new model-theoretic tools to understand homogeneous structures and in particular those that are NIP. There are few general theorems on homogeneous structures and at the same time no evidence that there cannot be any: we do not know how complicated homogeneous structures can be and this project hopes to shed light on this.The starting point of this project is the classification of the primitive rank 1 NIP homogeneous structures obtained by the PI. One goal is naturally to generalize this result to all finite rank NIP homogeneous structures. A more long-term goal is the classification of all NIP homogeneous structures. This would require understanding omega-categorical linear orders, which is an interesting project in its own right. A more general goal of the project is the development of model-theoretic tools to study homogeneous structures. This will build on the work mentioned above as well as on a previous work with Itay Kaplan on finitely generated dense subgroups of automorphism groups. Projects include finding model-theoretic consequences of the Ramsey property and clarifying its link with distality, finding necessary and sufficient conditions for admitting homogeneous expansions with nice properties (including having a stationary or canonical independence relation, being linearly ordered, Ramsey etc.). Finally, a more speculative project is the understanding of random-like behaviors in homogeneous structures and finding ways to measure the complexity of homogeneous structures, in particular those that lie outside the usual model-theoretic tame classes.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

模型论是数理逻辑的一个分支，它研究数学结构（即具有某些运算的集合）的组合性质。由于大多数数学对象都可以表示为结构，因此它的主题非常广泛，并且与数学的几个领域相互作用。然而，其他数学领域对特定的结构或结构类感兴趣（例如算术研究加法和乘法的整数结构），模型论则后退一步，研究一般的结构，寻找分界线和共同性质。它挑出由组合驯服条件定义的大类结构（这意味着结构在某种意义上并不太复杂），然后试图理解这些类中的结构。其中一类是NIP结构，它可以被认为是具有几何风格的结构。这门课在过去的十年里受到了很多关注。另一类是同质结构，也就是有很多对称性的结构。这些都是属于组合学的对象，并且已经在外部或模型论的边界进行了大量研究。该项目的主要目标是研究新的模型理论工具，以了解均匀结构，特别是那些NIP。关于齐次结构的一般定理很少，同时也没有证据表明不可能有：我们不知道齐次结构有多复杂，本项目希望阐明这一点。本项目的出发点是由PI获得的原始秩1 NIP齐次结构的分类。一个目标自然是推广这一结果的所有有限秩NIP齐次结构。更长期的目标是对所有NIP均质结构进行分类。这需要理解欧米伽范畴线性序，这本身就是一个有趣的项目。该项目的一个更普遍的目标是开发模型理论工具来研究均匀结构。这将建立在上面提到的工作以及以前的工作与Itay Kaplan对生成稠密子群的自同构群。项目包括寻找Ramsey属性的模型理论后果，并澄清其与远端的联系，找到允许具有良好属性的齐次展开的必要和充分条件（包括具有固定或正则独立关系，线性有序，Ramsey等）。最后，一个更具投机性的项目是理解均匀结构中的类随机行为，并找到测量均匀结构复杂性的方法，特别是那些位于通常的模型理论驯服类之外的结构。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

项目成果

Model Checking on Interpretations of Classes of Bounded Local Cliquewidth

有界局部团宽度类解释的模型检查

• DOI: 10.1145/3531130.3533367
• 发表时间: 2022
• 期刊: LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
• 作者: Bonnet, Édouard;Dreier, Jan;Gajarský, Jakub;Kreutzer, Stephan;Mählmann, Nikolas;Simon, Pierre;Toruńczyk, Szymon
• 通讯作者: Toruńczyk, Szymon

Twin-width IV: ordered graphs and matrices

• DOI: 10.1145/3519935.3520037
• 发表时间: 2021-02
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: 'Edouard Bonnet;Ugo Giocanti;P. D. Mendez;Pierre Simon;St'ephan Thomass'e;Szymon Toruńczyk