Random Structures: Concentration, Combinatorial Statistics, and Beyond

Random structures, such as random graphs, are mathematical models for systems in which complex behavior emerges from many simple random choices. They arise throughout mathematics and science, including in the study of networks, randomized algorithms, and statistical methods for drawing conclusions from large datasets with many variables. A central question, both mathematically and in applications, is when the key features of such random systems are predictable. In some cases, a quantity of interest almost always lies in a narrow predictable range, while in other cases its possible values can spread out in more complicated ways. This kind of predictability, known as concentration, is a basic theme in the mathematics of random discrete systems. It also plays an important role in statistics, where it helps determine what can and cannot be learned from noisy data. Closely related are phase transitions, where a small change in an underlying parameter can abruptly change what is possible, for example whether a hidden pattern can be detected or recovered. This project develops new mathematical theory for understanding these phenomena in random graphs, related random structures, and statistical problems involving noisy data, especially in settings where current methods do not yet give satisfactory answers. This project has the potential to benefit society by strengthening the mathematical foundations used to reason about uncertainty in large networks and high-dimensional data, through outreach to K–12 STEM students, and by providing research and training opportunities for undergraduate and graduate students. The main theme of this project is to develop new probabilistic and combinatorial tools for concentration and phase-transition phenomena at the interface of random structures and combinatorial statistics. The first research thrust addresses fundamental gaps in our understanding of concentration in random structures. One goal is to resolve long-standing questions about the extent of concentration of key combinatorial parameters in random graphs, including the domination number, by developing new approaches and proof techniques for sparse random graphs. A second goal is to develop a new approach for characterizing the concentration behavior of number-theoretic extremal parameters in random subsets of the integers. Another goal is to establish new local central limit theorems in random structures. The second research thrust focuses on combinatorial statistics, especially high-dimensional estimation and testing problems in which random structures model both signal and noise, with planted subgraph models as a well-known example. One goal is to use random graph ideas to study the fine behavior of statistical estimation problems near phase-transition thresholds and, conversely, to use statistical testing ideas to address long-standing conjectures in random graph theory. Together, these research thrusts aim to advance the theory of random structures and to create new connections between probabilistic combinatorics and high-dimensional statistics, paving the way for further advances in both fields. 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.