Random Combinatorial Structures

随机组合结构

• 批准号: 0406024
• 负责人: Boris Pittel
• 金额: $ 10万
• 依托单位: Ohio State University Research Foundation -DO NOT USE
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-15 至 2008-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0406024&HistoricalAwards=false
• 关键词: Random; Combinatorial; Structures

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.

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