9803410 Pittel The investigator will study a series of interrelated problems in asymptotic enumeration and combinatorial probability. The goal is to analyze likely and unlikely behavior of large combinatorial structures such as random graphs, trees, permutations, and partitions of sets and integers. This research will develop new approaches based on combinatorial-algebraic principles and ideas and analytical methods of probability and random processes. The connection between combinatorics and probability is well known. It played a major role in the early stages of development of probability theory, and some classical problems of a combinatorial nature are traditionally used to illustrate how the general theorems work in application to combinatorics. Among them are random walks and allocations of particles among cells (boxes), the latter being quite popular in various models of statistical mechanics. During the last 30-35 years, there has been a tremendous outpouring of research in combinatorial probability motivated by new problems in statistical mechanics (percolation theory, for instance), polymerization theory, computer science (probabilistic analysis of combinatorial algorithms), population genetics, etc. The terms random permutations, mappings, graphs, partitions, etc. have become household names for many researchers who have discovered the importance of analysis of random combinatorial structures. The related theory of random graphs, inaugurated by Erdos and Renyi in the early sixties, has been found indispensable in many important applications. Characteristically, the deepest results have come via a combination of fine combinatorial techniques and powerful probabilistic methods. Besides the problems directly related to random graphs, the investigator will study an optimal assignment problem with random costs, a possible connection between the evolving random graph and the Diaconis- Shahshahani algorithm ("card shuffling") for generating a r andom permutation, and various problems on random partitions of sets and integers. The accent will be made on searching for probabilistic and analytic methods which can be used for other combinatorial structures important in applications.
