Descriptive Combinatorics and Ergodic Theory

本项目研究图的描述性集合论方面。一个熟悉的图形例子是互联网：一个由计算机组成的巨大网络，由电缆连接。随着时间的推移，很容易想象这个网络会变得如此之大，以至于涉及单个计算机几乎是不可能的。取而代之的是，人们可以探索大量的集合，并提出这样的问题：“我需要多少个标签，这样才不会有两台相连的计算机收到相同的标签？”这个称为图的色数的参数可以根据允许产生标记的算法的复杂性而变化。这些参数与其他数学领域有(通常令人惊讶的)联系，包括组合和几何群论、概率论和算子代数，该项目的次要目标是除了锻造新的联系之外，还加强这些联系。在这种一般背景下，更精确的拟议研究领域包括：(A)可测顶点着色、边着色、匹配和子森林的存在，(B)可测量等价关系的可构造性的应用，特别是那些作为局部紧波兰群的保概率度量作用的轨道等价关系出现的等价关系，(C)应用于寻找群行动的可测量平铺，以及(D)用来刻画矛盾分解的应用。这项研究将特别关注遍历理论的应用，将作用群的代数性质与其相关图形等价关系的可测量组合性质联系起来。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This project investigates descriptive set-theoretic aspects of graphs. A familiar example of a graph is the internet: a huge network of computers, connected by cables. Over time, it is easy to imagine this network growing so large that referring to individual computers becomes next to impossible. Instead, one can probe large collections and ask questions like "how many labels do I need so that no two connected computers receive the same label?" This parameter, called the chromatic number of the graph, can change depending upon the complexity of the algorithms allowed to produce the labeling. Such parameters have (often surprising) connections with other areas of mathematics -- including combinatorial and geometric group theory, probability theory, and operator algebras -- and a secondary aim of this project is to strengthen these connections in addition to forging new ones.More precise proposed areas of study within this general setting include: (a) existence of measurable vertex colorings, edge colorings, and matchings, and subforests, (b) applications to structurability of measured equivalence relations, in particular those arising as orbit equivalence relations of probability-measure-preserving actions of locally compact Polish groups, (c) applications to finding measurable tilings of group actions, and (d) applications towards characterizing paradoxical decompositions. Particular attention will be paid to ergodic-theoretic applications of this study, connecting algebraic properties of an acting group with measurable combinatorial properties of its associated graphed equivalence relation.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.