Random Combinatorial Structures and Algorithms

随机组合结构和算法

• 批准号: 9803410
• 负责人: Boris Pittel
• 金额: --
• 依托单位: Ohio State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-06-15 至 2002-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9803410&HistoricalAwards=false
• 关键词: Random; Combinatorial; Structures; Algorithms

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.

9803410 Pittel研究员将研究渐近枚举和组合概率中的一系列相互关联的问题。目标是分析大型组合结构（例如随机图、树、排列以及集合和整数的划分）的可能和不可能行为。这项研究将开发基于组合代数原理和思想以及概率和随机过程分析方法的新方法。组合数学和概率之间的联系是众所周知的。它发挥了重要作用，在早期阶段的发展概率论，和一些经典问题的组合性质传统上用来说明如何工作的一般定理的应用组合。其中包括随机游走和粒子在细胞（盒子）之间的分配，后者在统计力学的各种模型中非常流行。在过去的30-35年里，在统计力学的新问题的推动下，对组合概率的研究大量涌现（例如渗流理论）、聚合理论、计算机科学（组合算法的概率分析），群体遗传学等。术语随机排列，映射，图形，分区，等已经成为许多研究人员的家喻户晓的名字，他们已经发现了随机组合结构分析的重要性。由Erdos和Renyi在60年代初开创的随机图的相关理论在许多重要的应用中是不可缺少的。典型的，最深刻的结果已经通过精细的组合技术和强大的概率方法的组合。除了与随机图直接相关的问题外，研究人员还将研究具有随机成本的最优分配问题，不断发展的随机图与Diaconis- Shahshahani算法（“洗牌”）之间的可能联系，用于生成随机排列，以及集合和整数的随机分区的各种问题。重点是寻找可用于应用中重要的其他组合结构的概率和分析方法。