Descriptive Combinatorics and Group Actions

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

This research project is in the discipline of descriptive set theory: the analysis of sets of numbers by the complexity or simplicity of their description. While abstract set theory is replete with counterintuitive pathologies (such as splitting a ball into five pieces and reassembling them into two copies of the original ball), many of these are circumvented by imposing constraints on the definition of the sets involved. Moreover, the search for definable solutions to some question is often tied closely with the study of algorithms in computer science. In this fashion, algorithms for analyzing configurations in large finite networks often correspond to descriptive set-theoretically simple solutions to infinite problems, and there are notable examples of the infinite analysis shedding light on the finite counterparts as well. Drawing out further connections between these finite and infinite settings is a major focus of the project, which is accessible to student researchers as well as more advanced mathematicians. The project includes the training of undergraduate and graduate students. More specifically, the project applies descriptive set-theoretic methods to examine the structure of definable graphs. Such graphs often arise in topological dynamics and ergodic theory, and in particular their combinatorial properties are often intertwined with algebraic aspects of the acting group. Specific combinatorial problems under investigation include: determining definable chromatic numbers of graphs, identifying when matchings and circulations can be found, and characterizing when such graph admit useful acyclic subgraphs. The project also explores applications of these ideas towards finding tilings of group actions and understanding the equidecomposability relation arising from such actions. These topics are all closely tied with the local model of distributed computing in theoretical computer science and also have interactions with finite combinatorics, graph limits, probability, and geometric group theory. 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.