Descriptive Combinatorics and Group Actions

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

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.