Mathematical Sciences: The Probabilistic Method

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

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.