Mathematical Sciences: The Probabilistic Method

数学科学：概率方法

• 批准号: 9623067
• 负责人: Joel Spencer
• 金额: $ 11.7万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-06-01 至 1999-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9623067&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Probabilistic; Method

Spencer The Probabilistic Method has been developed intensively and become one of the most powerful and widely used tools applied in Combinatorics. In this methodology, as developed by Paul Erdos, one proves the existence of a combinatorial object by showing that a suitably defined random object has the desired properties with positive probability. Closely aligned is the study of Random Graphs and other Random Structures. Also closely aligned is the analysis of Randomized Algorithms in Computer Science. A particular set of problems in this investigation involve radom greedy algorithms, which combine all of these elements. Asymptotic packing is a problem of current interest. Given a family of objects, one wants a disjoint subfamily, a packing, taking up as much space as possible. Results over the past decade have given general conditions such that almost all of the space can be covered. This project considers bounds on the amount of space not covered. Recent years have seen the use of more subtle probability methods in this area. Martingales have long been a powerful tool for probabilists, but now we are seeing how to use them to give strong bounds on discrete problems. The Lovasz Local Lemma and probability inequalities of Jason and Talagrand are used to good effect. Random algorithms are analyzed via birth processes and differential equations. The percolation of the random graph when average degree is near one is analagous to bond percolation in the plane near critical probability. For random graphs, the appropriate reparameterization is known. For bond percolation on the n by n grid, an analogous result is in sight. The random graph percolation also corresponds to a birth process with the expected family size near one. This gives new insight into the random graph model and led to a surprising connection between enumeration of graphs and a conditional form of Brownian motion. This research is in the general area of Combinatorics. One of the goals of Combinat orics is to find efficient methods to study how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.

Spencer 概率方法得到了广泛的发展，成为组合学中应用最强大、使用最广泛的工具之一。在 Paul Erdos 开发的这种方法中，人们通过证明适当定义的随机对象具有正概率的所需属性来证明组合对象的存在。紧密结合的是随机图和其他随机结构的研究。计算机科学中随机算法的分析也密切相关。本研究中的一组特定问题涉及随机贪婪算法，该算法结合了所有这些元素。渐近堆积是当前人们感兴趣的问题。给定一个对象族，我们想要一个不相交的子族，一个包装，占用尽可能多的空间。过去十年的结果给出了一般条件，几乎可以覆盖所有空间。该项目考虑了未覆盖空间量的界限。 近年来，在这一领域出现了更微妙的概率方法的使用。长期以来，马丁格尔一直是概率学家的强大工具，但现在我们正在了解如何使用它们来为离散问题给出强有力的界限。 Lovasz 局部引理以及 Jason 和 Talagrand 的概率不等式的使用取得了良好的效果。通过出生过程和微分方程来分析随机算法。当平均度接近 1 时随机图的渗流类似于临界概率附近平面中的键渗流。对于随机图，适当的重新参数化是已知的。对于 n × n 网格上的键渗透，类似的结果就在眼前。随机图渗透也对应于预期家庭规模接近 1 的出生过程。这为随机图模型提供了新的见解，并导致图的枚举与布朗运动的条件形式之间存在令人惊讶的联系。 这项研究属于组合学的一般领域。 Combinat orics 的目标之一是找到有效的方法来研究如何排列离散的对象集合。离散系统的行为对于现代通信极其重要。例如，大型网络的设计（例如电话系统中的网络）以及计算机科学中处理离散对象集的算法设计，都利用了组合研究。