The goal of this project is to use the results, methods, and techniques that originate in combinatorics to address problems in logic, ergodic theory, and topological dynamics. Combinatorics is the area of mathematics concerning discrete structures, such as graphs, which can be viewed as mathematical objects representing networks consisting of nodes with links between them. This area has experienced immense growth in the past several decades, owing in part to its close connection to computer science. Recently, it has become apparent that combinatorial insights can shed new light on problems in other, seemingly unrelated, areas, such as ergodic theory - the study of the evolution of dynamical systems, encompassing a range of applications from epidemic models to planetary motion. It turns out that one can often associate a graph or another discrete structure to a dynamical system and then use combinatorial methods to elucidate its properties. The goals of this project are to extend the range of applications of this approach and develop new powerful combinatorial tools for the needs of other areas. The PI will work with graduate and undergraduate students through problem solving workshops and other collaborations.
More specifically, this project revolves around transferring ideas from graph coloring theory and probabilistic combinatorics to the setting where it is necessary to fulfill additional regularity constraints (measure-theoretic, topological, etc.). Particular avenues of investigation that will be covered in this project include: (a) studying the extent to which classical probabilistic tools, especially the Lovász Local Lemma, can be extended to the measurable framework; (b) finding new methods for building measurable colorings, matchings, and other useful structures in graphs; (c) applying combinatorial techniques to attack major open problems in dynamical systems, such as the entropy problem and the Ellis problem; and (d) studying the interplay between descriptive set theory and computer science.
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.
