Mathematical Sciences: The 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.