Random Combinatorial Structures

我们计划研究几种随机结构，如随机图和映射，随机Young表和平面整数分区。虽然在Erdos-Renyi随机图过程的分析方面取得了巨大的进展，但对该过程的有向图版本的过渡行为知之甚少。一个障碍是缺乏有向图的枚举结果。在与wormald的合作中，发起人计划利用他们之前对无向图的研究中的一些思想，通过顶点度来研究有向图的渐近计数。支持者相信这项研究将导致在随机有向图中对相变的详细描述。支持者计划分析Lovasz提出的另一种图处理方法，其中新边的出现概率与产生的顶点度成正比。这种分析需要解决大量经典图枚举问题的自然扩展。受Propp和Wilson以及Dalal-Schmutz工作的启发，支持者计划研究独立随机映射组合的坍缩时间。支持者将继续研究随机平面图和立体图的可能形状，并试图回答最近与Borgs， Chayes和Mertens共同进行的关于最优划分问题的两项研究中提出的开放性问题。无论多么理想化，随机图方法都提供了一种描述大型演化网络动态的方法。我们希望我们在图过程上的工作将有助于更好地理解现实生活中网络的“突变”现象特征，当添加少量连接导致形成紧密的“核心”时。我们对划分问题的持续研究将提供更深入的见解，以了解其算法复杂性对随机输入参数之间关系的关键依赖。我们相信，这一分析将成为研究更广泛的组合优化问题的一个模型，这些问题在应用中很重要，比如“背包”问题和“装箱”问题。

We plan to study several random structures, such as the random graphs andmappings, the random Young tableaux and the plane integer partitions. Whilea tremendous progress has been achieved in analysis of the Erdos-Renyi random graph process, much less is known about the transitional behavior of thedirected graph version of this process. One obstacle is a dearth ofenumeratve results for directed graphs. In cooperation with Wormaldthe 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 dynamicsof large evolving networks. We hope that our work on the graph processes will contribute to a better understanding of an "abrupt change" phenomenon characteristicfor 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 insightinto critical dependence of its algorithmic complexity on the relations between the randominput parameters. We believe that this analysis will serve as a modelfor study of a broader class of combinatorial optimization problems important inapplications, such as the "knapsack" problem and the "bin packing" problems.