The Interplay between Combinatorics, Set Theory, and Dynamics

这个项目的目标是使用的结果，方法和技术，起源于组合，以解决问题的逻辑，遍历理论和拓扑动力学。组合数学是关于离散结构的数学领域，例如图，它可以被视为表示由节点组成的网络的数学对象，节点之间有链接。这一领域在过去几十年中经历了巨大的增长，部分原因是它与计算机科学的密切联系。最近，很明显，组合的见解可以为其他看似无关的领域的问题提供新的见解，例如遍历理论-动力系统演化的研究，涵盖了从流行病模型到行星运动的一系列应用。事实证明，人们通常可以将一个图或另一个离散结构与一个动力系统联系起来，然后使用组合方法来阐明其性质。该项目的目标是扩展这种方法的应用范围，并开发新的强大的组合工具，以满足其他领域的需求。PI将通过解决问题的研讨会和其他合作与研究生和本科生合作。更具体地说，这个项目围绕转移思想从图着色理论和概率组合学的设置，它是必要的，以满足额外的正则性约束（测量理论，拓扑等）。本计画将涵盖的特定研究途径包括：（a）研究古典机率工具，特别是Lovász局部引理，可延伸至可量测架构的程度;（B）寻找新的方法，以建立可量测着色、匹配及其他有用的图结构;（c）应用组合技术解决动力系统中的主要未决问题，例如熵问题和埃利斯问题;以及（d）研究描述集合论与计算机科学之间的相互作用。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The goal of this project is to use the results, methods, and techniques that originate in combinatorics to address problems in logic, ergodic theory, and topological dynamics. Combinatorics is the area of mathematics concerning discrete structures, such as graphs, which can be viewed as mathematical objects representing networks consisting of nodes with links between them. This area has experienced immense growth in the past several decades, owing in part to its close connection to computer science. Recently, it has become apparent that combinatorial insights can shed new light on problems in other, seemingly unrelated, areas, such as ergodic theory - the study of the evolution of dynamical systems, encompassing a range of applications from epidemic models to planetary motion. It turns out that one can often associate a graph or another discrete structure to a dynamical system and then use combinatorial methods to elucidate its properties. The goals of this project are to extend the range of applications of this approach and develop new powerful combinatorial tools for the needs of other areas. The PI will work with graduate and undergraduate students through problem solving workshops and other collaborations. More specifically, this project revolves around transferring ideas from graph coloring theory and probabilistic combinatorics to the setting where it is necessary to fulfill additional regularity constraints (measure-theoretic, topological, etc.). Particular avenues of investigation that will be covered in this project include: (a) studying the extent to which classical probabilistic tools, especially the Lovász Local Lemma, can be extended to the measurable framework; (b) finding new methods for building measurable colorings, matchings, and other useful structures in graphs; (c) applying combinatorial techniques to attack major open problems in dynamical systems, such as the entropy problem and the Ellis problem; and (d) studying the interplay between descriptive set theory and computer science.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.