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)目前对上述一般阈值猜想最有希望的攻击路线更多是傅里叶解析而不是组合，并且起源于近30年前PI及其合作者在理论计算机科学问题上的工作（尽管此后发生了很多事情）。

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.