Descriptive Combinatorics and Group Actions

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

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.