Descriptive set-theoretic graph theory and applications

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.