Descriptive Combinatorics and Group Actions

描述性组合和群动作

• 批准号: 2154160
• 负责人: Clinton Conley
• 金额: $ 24.43万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2154160&HistoricalAwards=false
• 关键词: Descriptive; Combinatorics; Group; Actions

This research project is in the discipline of descriptive set theory: the analysis of sets of numbers by the complexity or simplicity of their description. While abstract set theory is replete with counterintuitive pathologies (such as splitting a ball into five pieces and reassembling them into two copies of the original ball), many of these are circumvented by imposing constraints on the definition of the sets involved. Moreover, the search for definable solutions to some question is often tied closely with the study of algorithms in computer science. In this fashion, algorithms for analyzing configurations in large finite networks often correspond to descriptive set-theoretically simple solutions to infinite problems, and there are notable examples of the infinite analysis shedding light on the finite counterparts as well. Drawing out further connections between these finite and infinite settings is a major focus of the project, which is accessible to student researchers as well as more advanced mathematicians. The project includes the training of undergraduate and graduate students. More specifically, the project applies descriptive set-theoretic methods to examine the structure of definable graphs. Such graphs often arise in topological dynamics and ergodic theory, and in particular their combinatorial properties are often intertwined with algebraic aspects of the acting group. Specific combinatorial problems under investigation include: determining definable chromatic numbers of graphs, identifying when matchings and circulations can be found, and characterizing when such graph admit useful acyclic subgraphs. The project also explores applications of these ideas towards finding tilings of group actions and understanding the equidecomposability relation arising from such actions. These topics are all closely tied with the local model of distributed computing in theoretical computer science and also have interactions with finite combinatorics, graph limits, probability, and geometric group theory.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.

该研究项目在描述性集理论的学科中：通过其描述的复杂性或简单性来分析数字集。 虽然抽象集理论充满了违反直觉的病理（例如将球分成五个部分并将其重新组装成两个原始球的两个副本），但其中许多是通过对所涉及集合的定义的构成约束来避免的。 此外，寻找某个问题的可确定解决方案通常与计算机科学算法的研究紧密相关。 以这种方式，用于分析大量有限网络中配置的算法通常对应于描述性的理论上简单的解决方案，解决了无限问题，并且有明显的例子，即无限分析也阐明了有限的对应物。 这些有限和无限设置之间的进一步联系是该项目的主要重点，该项目可用于学生研究人员以及更高级的数学家。该项目包括对本科生和研究生的培训。更具体地说，该项目应用描述性设置理论方法来检查可定义图的结构。 这些图通常是在拓扑动力学和千古理论中出现的，尤其是它们的组合特性通常与代理群体的代数方面交织在一起。调查中的特定组合问题包括：确定图形的可定义色数，识别何时可以找到匹配和循环，并表征该图何时允许有用的无环子图。该项目还探讨了这些思想在寻找团体行动的瓷砖方面的应用，并了解这种行动引起的等分可使性关系。 这些主题都与理论计算机科学中的分布式计算的本地模型紧密相关，并且还与有限的组合学，图形限制，概率和几何群体理论有着相互作用。该奖项反映了NSF的法定任务，并被认为是通过使用该基金会的智力和更广泛影响的评估来审查CRITERIA的评估来通过评估来获得支持的。