Descriptive set-theoretic graph theory and applications

在这项研究建议的中心研究对象是组合图，这是一个基本的顶点，其中一些对连接的边缘和一些对保持不连接的集合组成的结构。 尽管这个概念很简单，任何玩过连接点游戏的孩子都很熟悉，但图形足够普遍，可以模拟数学和附近科学学科中的许多现象。 例如，图已经在计算机网络设计中找到了应用，包括建模互联网的演变，以及在统计物理学中，包括建模原子尺度的热力学相互作用。 在这些应用中，顶点的数量是如此之大，以至于为了分析的目的，它是无法区分的无限。 在这个项目中，主要研究者将从描述性集合论的角度研究无限图，本质上将这些图抽象为集合，并将其描述的复杂性与其具体的组合性质联系起来。 在数学领域，如动力学和概率，这样的可定义图出现有限图的极限，和描述集理论的方法揭示了这种渐近行为。 此外，分析发现应用在描述集理论以及，找到新的方法分层的相对困难的各种分类problems.In一般情况下，该项目的目标是了解组合参数的标准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.