Thresholds and asymptotics

点击翻译按钮获取中文摘要

This project focuses on two of the PI's current interests, thresholds for random structures and asymptotic enumeration, with somewhat more emphasis on the former. Roughly speaking, a threshold is the point at which some event of interest in a random system becomes likely as some intensity parameter increases. Understanding when this happens has long been a central concern of probabilistic combinatorics and related areas, particularly theoretical computer science and statistical physics. For example, thresholds have been a main focus of the theory of random graphs since its initiation by Erdos and Renyi fifty years ago. They are closely tied to the theory of percolation, a basic model of statistical mechanics dating to work of Broadbent and Hammersley in 1957. (It was, however, some decades before the connections between these disciplines began to be appreciated). Asymptotic enumeration of the type considered in this project is concerned with estimating rates of growth of various combinatorially interesting families (e.g. graphs without triangles or functions representable by k-SAT formulae) in situations where traditional generating functions techniques seem to be of little use.Several of the problems considered in the proposal have roots in related disciplines (one general theme underlying much of the material is that complicated structures can often be usefully approximated by simpler ones), though the focus is primarily on what appears to be mathematically fundamental. These problems are simple and seemingly basic questions that have long resisted solution. Attacking such questions requires one to go beyond existing methods, and to find and exploit connections with other parts of mathematics. Despite the probable difficulty of the main questions considered, recent progress by the PI and coauthors gives hope of further developments and even full resolutions of some of them. There are also many interesting lesser (sub- or related) problems that may prove more tractable.