Descriptive set-theoretic graph theory and applications

本研究计划的中心研究对象是组合图，组合图是由底层顶点集合组成的结构，其中一些顶点对通过边连接，而另一些顶点对则保持不连接。尽管这个概念很简单，任何玩过“连点”游戏的孩子都很熟悉，但图形足够普遍，可以在数学和附近的科学学科中为许多现象建模。例如，图形已经在计算机网络设计中找到了应用，包括为互联网的演变建模，以及在统计物理学中，包括为原子尺度的热力学相互作用建模。在这些应用中，顶点的数量是如此之大，以至于对于分析目的来说，它与无穷大难以区分。在这个项目中，首席研究员将从描述集合论的观点研究无限图，本质上是将这些图抽象地视为集合，并将其描述的复杂性与其具体的组合特性联系起来。在数学领域，如动力学和概率论，这种可定义的图作为有限图的极限出现，描述性集合论方法阐明了这种渐近行为。此外，分析也发现了描述性集合理论中的应用，找到了对各种分类问题的相对难度进行分层的新方法。总的来说，该项目的目标是了解受各种可测量性约束的标准Borel空间上Borel图的组合参数。例如，当要求着色函数是Borel（相对于某些Borel概率测量可测量的，或相对于某些兼容的波兰拓扑可测量的）时，图的色数（为相邻顶点分配不同值的函数图像的最小基数）通常具有不同的值。虽然这些参数本身就很有趣，但它们与数学的其他领域（包括组合和几何群论、遍历理论、概率论和算子代数）有着（通常令人惊讶的）联系。除了建立新的联系外，该提议的第二个目的是加强这些联系。在这一总体背景下，更精确的建议研究领域包括：(a)可测顶点着色、边着色和匹配的存在性；(b)在可测等价关系可构性中的应用，特别是局部紧化波兰群的保概率-测度作用的轨道等价关系；(c)在可定义等价关系Borel/测度可约性的全局层次中的应用，特别是超有限以上的可定义等价关系；(d)与图极限概率方面的联系。

The central objects of study in this research proposal are combinatorial graphs, which are structures consisting of a underlying collection of vertices, some pairs of which are connected by edges and some pairs remaining unconnected. Despite the simplicity of this concept, familiar to any child who has played a game of connect-the-dots, graphs are sufficiently general to model many phenomena both within mathematics and also in nearby scientific disciplines. For example, graphs have found applications in computer network design, including modeling the evolution of the internet, as well as in statistical physics, including modeling atomic-scale thermodynamic interactions. In these applications, the number of vertices is so large that for analytical purposes it is indistinguishable from being infinite. In this project, the principal investigator will study infinite graphs from the descriptive set-theoretic viewpoint, in essence regarding such graphs abstractly as sets and relating the complexity of their descriptions with their concrete combinatorial properties. In areas of mathematics such as dynamics and probability, such definable graphs arise as limits of finite graphs, and the descriptive set-theoretic methods shed light on this asymptotic behavior. Additionally, the analysis finds applications within descriptive set theory as well, finding new ways of stratifying the relative difficulty of various classification problems.In general, the objective of the project is to understand combinatorial parameters of Borel graphs on standard Borel spaces subject to various measurability constraints. For example, the chromatic number of a graph (the smallest cardinality of the image of a function assigning different values to adjacent vertices) typically has different values when the coloring function is required to be Borel, measurable with respect to some Borel probability measure, or Baire measurable with respect to some compatible Polish topology. While interesting in their own right, such parameters have (often surprising) connections with other areas of mathematics -- including combinatorial and geometric group theory, ergodic theory, probability theory, and operator algebras -- and a secondary aim of the proposal 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, (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 the global hierarchy of Borel/measure reducibility of definable equivalence relations, especially those just above hyperfinite, (d) connections with the probabilistic aspects of graph limits.