Computability, combinatorics, and topology

About This Grant

This project is set at the interface of two areas in the foundation of mathematics, computability theory and reverse mathematics. Computability theory, which traces its history to the pioneering work of Alan Turing in the 1930s on the formal definition of an algorithm, is broadly concerned with the question of which mathematical problems can be solved by a computer, and among those that cannot be, in measuring precisely how far away these problems are from being thus solvable. Reverse mathematics instead looks to understand how complicated mathematical theorems are, by determining the minimal axioms necessary to carry out the logical arguments in the proofs of these results. Although these areas are distinct, they are deeply related, with ideas and results in one often leading to ideas and results in the other. Together, they provide deep insight across all areas of mathematics, revealing connections between previously disparate areas, and often leading to novel and more computationally efficient methods. This project involves graduate students. A longstanding focus of research in computability theory and reverse mathematics has been combinatorics, especially Ramsey’s theorem and related combinatorial results. But more recent work has exposed fascinating new connections with other areas, including set theory and topology, which the PI is building on and exploring in this project. More precisely, the PI addresses a suite of problems concerning two important generalizations of Ramsey’s theorem: Milliken’s tree theorem, which comes from work in structural Ramsey theory, and the Ginsburg–Sands theorem, which is a purely topological result. Investigation of these theorems in computability theory and reverse mathematics over the past few years has already produced some significant developments, yet some of the most fundamental questions remain open. This project will seek to answer these questions, including through the development of new techniques and conceptual tools with which to approach problems in computable combinatorics more generally. In this way, the project will also further develop the interplay between computability theory, combinatorics, and topology. 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.