Problems in Probabilistic Combinatorics

概率组合学问题

• 批准号: 1501962
• 负责人: Jeffry Kahn
• 金额: $ 48万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-06-01 至 2024-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1501962&HistoricalAwards=false
• 关键词: Problems; Probabilistic; Combinatorics

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.

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