Statistical Physics Methods in Combinatorics

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

The study of typical or random discrete structures in combinatorics and probability theory has become invaluable to understanding the modern world, from understanding the performance of algorithms on typical instances, to understanding the properties of large computer, social, or logistics networks. Developing powerful mathematical techniques to study random discrete structures can provide rigorous insight and a deep understanding of the behavior of these models. This project will use the ideas, methods, and intuition from the field of statistical physics to answer questions, discover new phenomena, and develop new methods in combinatorics and probability. The project will study the phase transition phenomenon in combinatorial enumeration problems and in large deviation problems in probability theory. As part of the project the PI will organize activities bringing together researchers from different fields, including combinatorics, probability, statistical physics, and algorithms. The project will also feature yearly workshops for Atlanta-area high school students, introducing the students to accessible and exciting topics in math and computer science related to the research aims of the project. One of the major aims of combinatorics is to understand the number and typical structure of large combinatorial objects, such as graphs without a forbidden subgraph, or sets of integers without certain arithmetic patterns. Methods developed to study such problems include the regularity method, the method of graph and hypergraph containers, and large deviation inequalities like Janson's Inequality. This project will use new methods based on tools like the cluster expansion from statistical physics and algorithmic tools from the study of approximate counting and sampling to prove precise results on asymptotic enumeration and typical structure in the settings above, and to dive into the critical regime in which global structure emerges in typical objects, such as when a typical triangle-free graph of a given edge density begins to align with a bipartition of the vertices. This emergence of global structure is analogous to order-disorder phase transitions in statistical physics models like the Ising model, and the aim of this project is to study the details of such phase transitions in combinatorial problems and in the study of large deviations in random graphs. 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.