Problems in Probabilistic Combinatorics

该项目的中心焦点是组合学和概率论边界上的几个相互关联的问题。提出的问题延伸到了其他领域，如经典的渐近计数、代数拓扑和概率真。该项目的一个主要主题是努力了解在(大型)离散随机系统中出现各种感兴趣的属性的“阈值”强度。这是一个经典的领域(追溯到大约60年前，研究组合方面的随机图和概率方面的渗流)；但这也是一个近年来取得重大进展的领域，也是一个与其他几个学科密切联系的领域，包括统计物理和计算理论。虽然正在研究的问题是纯粹的数学问题，但这一学科领域的工作有时会产生相当意想不到的后果，无论是在数学领域还是在数学之外。这项研究项目的中心是简单而看似基本的问题和“谱系”，也就是抵制解决方案的实质性历史。攻击这样的问题是一种强迫自己超越现有方法的方式，这往往会导致发现和利用与数学其他部分和相关领域的新联系。正在研究的几个主要问题涉及理解各种经典事实和定理在随机环境中保持正确的程度；例如：(A)当(即，对于p=p(N))是随机图G(n，p)的“团复合体”(其简单是团的顶点集)可能具有消失的k维同调(例如，在整数或整数mod 2上)？(B)n-集合X的k-子集的随机集合F何时具有(“Erdos-Ko-Rado”)性质，即不包含两个不相交集合的最大子集合由包含X的某个固定元素的F的成员组成？在这些和其他情况下，进一步的进展似乎取决于更好地了解涉及独立利益的根本问题。该提案还提出了一些非常普遍的可能性，例如，一种关于独立事件的行为作为更复杂情况的指南，另一种(由于Kalai和PI)原则上将确定(高达不可避免的对数误差因子)完全任意增加的属性(某个有限宇宙的子集的阈值；粗略地说，该属性从不可能到可能的阈值)的阈值。虽然大多数标题问题都源于概率-组合，但与其他领域有实质性的联系-一些组合，其他的，特别是当涉及方法论时，更遥远；例如：(A)关于随机图中存在某些树的旧猜想的证明最终取决于(除其他外)为经典更新理论的抽样而不替换的版本开发准确的估计；(B)目前对上述一般阈值猜想最有希望的攻击路线更多地是傅立叶分析而不是组合，并且起源于(尽管自那以后发生了许多事情)PI和合著者在近30年前关于理论计算机科学的一个问题的工作。

The project's central focus is on several interrelated problems on the borders of combinatorics and probability. The questions raised spill over into other areas, such as classical asymptotic enumeration, algebraic topology, and probability proper. One major theme of the project is the effort to understand the "threshold" intensities at which various properties of interest appear in (large) discrete random systems. This is a classical area (going back to the beginnings, roughly 60 years ago, of studies of random graphs on the combinatorial side and percolation on the probabilistic); but it is also an area that has seen major progress in recent years, and one that enjoys close ties with several other disciplines, including statistical physics and the theory of computation. Though the questions under study are purely mathematical, work in this subject area has sometimes had quite unforeseen consequences, both in and beyond mathematics. This research project centers on simple and seemingly basic questions with "pedigrees," that is, substantial histories of resisting solution. Attacking such questions is a way of forcing oneself to go beyond existing methods, which often leads to finding and exploiting new connections with other parts of mathematics and related areas. Several of the main problems under study are concerned with understanding the extent to which various classical facts and theorems remain true in a random setting; for example: (a) When (i.e., for what p = p(n)) is the "clique complex" (whose simplices are the vertex sets of the cliques) of the random graph G(n,p) likely to have vanishing k-dimensional homology (e.g., over the integers or the integers mod 2)? (b) When does a random collection F of k-subets of an n-set X have the ("Erdos-Ko-Rado") property that a largest subcollection not containing two disjoint sets consists of the members of F containing some fixed element of X? In these and other cases, further progress appears to depend on better understanding underlying issues of independent interest. The proposal also suggests some very general possibilities, for example, one on behavior of independent events as a guide to more complicated situations, and another (due to Kalai and the PI) which would in principle determine (up to an unavoidable logarithmic error factor) the threshold for a completely arbitrary increasing property (of subsets of some finite universe; the "threshold" being, roughly speaking, where the property goes from unlikely to likely). Though most of the headline problems are of probabilistic-combinatorial origin, there are substantial connections with other areas --- some combinatorial, others, particularly when it comes to methodology, more distant; for instance: (a) the proof of an old conjecture on presence of certain trees in a random graph eventually depended (very much inter alia) on developing precise estimates for a sampling-without-replacement version of classical renewal theory; (b) the currently most promising line of attack on the general threshold conjecture mentioned above is more Fourier-analytic than combinatorial and originates (though much has happened since) in work of the PI and coauthors nearly thirty years ago on a problem from theoretical computer science.