Thresholds and asymptotics

该项目侧重于PI当前的两个兴趣，随机结构的阈值和渐近枚举，更侧重于前者。粗略地说，阈值是随机系统中某些感兴趣的事件随着强度参数的增加而变得可能的点。长期以来，理解这种情况何时发生一直是概率组合学和相关领域，特别是理论计算机科学和统计物理学关注的中心问题。例如，自Erdos和Renyi在50年前提出随机图理论以来，阈值一直是其主要关注的焦点。它们与渗透理论密切相关，渗透理论是统计力学的一个基本模型，可以追溯到1957年Broadbent和Hammersley的工作。（然而，几十年后，这些学科之间的联系才开始得到重视。）在这个项目中考虑的类型的渐近枚举涉及在传统生成函数技术似乎没有什么用处的情况下估计各种组合有趣族（例如，没有三角形的图或由k-SAT公式表示的函数）的增长率。提案中考虑的几个问题植根于相关学科（许多材料背后的一个普遍主题是，复杂的结构通常可以用更简单的结构有效地近似），尽管重点主要放在看似数学基础的东西上。这些问题都是简单而看似基本的问题，长期以来一直得不到解决。解决这类问题需要超越现有的方法，找到并利用与数学其他部分的联系。尽管所考虑的主要问题可能存在困难，但PI及其合著者最近的进展给了进一步发展甚至完全解决其中一些问题的希望。还有许多有趣的小问题（子问题或相关问题）可能更容易处理。

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.