Descriptive Combinatorics and Ergodic Theory

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

This project investigates descriptive set-theoretic aspects of graphs. A familiar example of a graph is the internet: a huge network of computers, connected by cables. Over time, it is easy to imagine this network growing so large that referring to individual computers becomes next to impossible. Instead, one can probe large collections and ask questions like "how many labels do I need so that no two connected computers receive the same label?" This parameter, called the chromatic number of the graph, can change depending upon the complexity of the algorithms allowed to produce the labeling. Such parameters have (often surprising) connections with other areas of mathematics -- including combinatorial and geometric group theory, probability theory, and operator algebras -- and a secondary aim of this project 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, and subforests, (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 finding measurable tilings of group actions, and (d) applications towards characterizing paradoxical decompositions. Particular attention will be paid to ergodic-theoretic applications of this study, connecting algebraic properties of an acting group with measurable combinatorial properties of its associated graphed equivalence relation. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.