Descriptive set-theoretic graph theory and applications

描述性集合论图论及其应用

• 批准号: 1500906
• 负责人: Clinton Conley
• 金额: $ 15.38万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2019-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1500906&HistoricalAwards=false
• 关键词: Descriptive; set; theoretic; graph; theory

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.

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