Descriptive Combinatorics and Ergodic Theory

这个项目研究图的描述集合论方面。一个熟悉的图表例子是互联网：一个巨大的计算机网络，通过电缆连接。随着时间的推移，很容易想象这个网络变得如此之大，以至于引用个人计算机几乎是不可能的。相反，人们可以探测大型集合，并问这样的问题：“我需要多少个标签才能使两台连接的计算机接收到相同的标签？”这个参数，称为图的色数，可以根据允许生成标记的算法的复杂性而改变。这些参数与数学的其他领域有（通常令人惊讶的）联系——包括组合和几何群论、概率论和算子代数——这个项目的第二个目标是加强这些联系，除了建立新的联系。在这一总体背景下，更精确的建议研究领域包括：(a)可测顶点着色、边着色、匹配和子森林的存在性；(b)在可测等价关系的可结构性中的应用，特别是在局部紧化波兰群的概率测度保持作用的轨道等价关系中的应用；(c)在寻找群作用的可测平铺方面的应用；(d)在描述悖论分解方面的应用。将特别关注本研究的遍历理论应用，将作用群的代数性质与其相关的图等价关系的可测量组合性质联系起来。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.