Probabilistic Limit Theorems in Optimization Problems
Time and place
12:30–1:30 PM on Monday, April 20th, 2026; MR 1128
Dr. Grigory Terlov (University of North Carolina)
Abstract
Random optimization problems arise naturally across mathematics, physics, and computer science. Prominent examples include the problems of Minimal Matching, Traveling Salesman, and Minimal Spanning Tree. Although these problems are easy to state, their analysis is notoriously difficult, and progress has historically required ideas drawn from a wide range of subjects. While the average behavior of many such models is now well understood, the question of limiting distributions remains largely open, with only a few notable exceptions. In this talk, I will discuss a positive-temperature variant of optimization problems on dense graphs, in which auxiliary randomness is introduced that biases sampling toward the optimal solution. In this setting, our results provide a unified framework encompassing the classical optimization problems mentioned above, and establish laws of large numbers and central limit theorems for the natural statistics of interest, including the log-partition function, the weight of a typical configuration, and Gibbs averages. Joint work with Partha S. Dey.
