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概率度量或BAIRE可测量。 尽管本身有趣，但此类参数与其他数学领域具有（通常令人惊讶的）联系（包括组合和几何群体理论，千古理论，概率理论和操作者代数），该提案的次要目的是增强这些连接以外的这些连接。 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高足限，（d）与图形限制的概率方面的连接。