Thresholds and asymptotics

这个项目集中在PI的两个当前兴趣上，随机结构的阈值和渐近计数，在某种程度上更强调前者。粗略地说，阈值是指当某个强度参数增加时，随机系统中可能发生的某些感兴趣的事件的点。了解这种情况何时发生一直是概率组合学和相关领域的核心问题，特别是理论计算机科学和统计物理。例如，门限自50年前由鄂尔多斯和仁义提出以来，一直是随机图理论的一个主要焦点。它们与渗流理论密切相关，渗流理论是统计力学的一个基本模型，可以追溯到布罗德本特和哈默斯利1957年的工作。(然而，直到几十年后，这些学科之间的联系才开始被认识到)。在传统的生成函数技术似乎没有什么用处的情况下，本项目中所考虑的类型的渐近计数涉及到估计各种组合有趣的族(例如，没有三角形的图或可由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.