Descriptive Combinatorics and Ergodic Theory

这个项目研究图的描述性集合论方面。图的一个熟悉的例子是互联网：一个由电缆连接的巨大的计算机网络。 随着时间的推移，很容易想象这个网络变得如此之大，以至于提到单个计算机几乎是不可能的。 相反，人们可以探测大型集合，并提出这样的问题：“我需要多少个标签，才不会有两台连接的计算机收到相同的标签？“这个参数，称为图的色数，可以根据允许产生标记的算法的复杂性而变化。 这些参数有（通常令人惊讶）与数学的其他领域的联系-包括组合和几何群论，概率论，和算子代数-和这个项目的第二个目的是加强这些连接除了锻造新的。更精确的建议研究领域在这个一般设置包括：（a）可测顶点着色、边着色、匹配和子森林的存在性，（B）可测等价关系的可结构性的应用，特别是作为局部紧波兰群的概率测度保持作用的轨道等价关系而产生的应用，（c）应用于寻找群作用的可测平铺，以及（d）应用于表征悖论分解。 特别注意将支付给遍历理论的应用，这项研究，连接代数属性的一个代理集团与可测量的组合属性，其相关的图形等价relation.This奖项反映了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.