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.

这个研究项目属于描述性集合论的学科：通过描述的复杂性或简单性来分析数字集合。 虽然抽象集合论充满了违反直觉的病态（例如将一个球分成五部分，然后将它们重新组装成原始球的两个副本），但其中许多都是通过对所涉及的集合的定义施加约束来规避的。 此外，对某些问题的可定义解决方案的搜索通常与计算机科学中的算法研究密切相关。 以这种方式，分析大型有限网络中的配置的算法通常对应于描述性的集合理论简单的解决方案，无限问题，有显着的例子，无限分析揭示了有限的同行。 绘制出这些有限和无限设置之间的进一步联系是该项目的主要重点，学生研究人员以及更高级的数学家都可以访问。该项目包括培训本科生和研究生。更具体地说，该项目应用描述性集合论方法来研究可定义图的结构。 这种图经常出现在拓扑动力学和遍历理论中，特别是它们的组合性质经常与作用群的代数方面交织在一起。正在研究的具体组合问题包括：确定图的可定义色数，识别何时可以找到匹配和循环，以及表征此类图何时允许有用的非循环子图。该项目还探讨了这些想法的应用，以找到组行动的tilings和理解equidecomposability从这些行动产生的关系。 这些主题都与理论计算机科学中分布式计算的局部模型紧密相关，并且与有限组合学、图极限、概率和几何群论相互作用。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响评审标准进行评估，被认为值得支持。