We plan to study several random structures, such as the random graphs and mappings, the random Young tableaux and the plane integer partitions. While a tremendous progress has been achieved in analysis of the Erdos-Renyi random graph process, much less is known about the transitional behavior of the directed graph version of this process. One obstacle is a dearth of enumeratve results for directed graphs. In cooperation with Wormald the proponent plans to work on asymptotic counts of digraphs by the vertex degrees, using some ideas of their prior research on undirected graphs. The proponent is confident that this study will result in a detailed description of the phase transition in the random digraph. The proponent plans to analyze an alternative graph process suggested by Lovasz, in which the new edges appear with probabilities proportional to the resulting vertex degrees. This analysis will require solving a host of natural extensions of classic graph enumeration problems. Inspired by the work of Propp and Wilson, and Dalal-Schmutz, the proponent plans to study the collapse time of the compositions of the independent random mappings. The proponent will continue a study of the likely shapes of random plane and solid diagrams, and will try to answer open questions formulated in two recent studies of an optimal partitioning problem, conducted jointly with Borgs, Chayes and Mertens.
However idealized, the random graph methodology provides a way to describe dynamics of large evolving networks. We hope that our work on the graph processes will contribute to a better understanding of an "abrupt change" phenomenon characteristic for real-life networks, when addition of few connections leads to formation of a tight "core". Our continued study of the partitioning problem will provide a deeper insight into critical dependence of its algorithmic complexity on the relations between the random input parameters. We believe that this analysis will serve as a model for study of a broader class of combinatorial optimization problems important in applications, such as the "knapsack" problem and the "bin packing" problems.
