Random Combinatorial Structures

随机组合结构

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

A classic example of a combinatorial structure is a network (a graph), described as a set of nodes (vertices) connected to their neighbors by links (arcs, edges). The networks (graphs) have long been used as abstract mathematical descriptions of real-life social and technological networks. In 1960 Erdos and Renyi began studying a mathematical model of a graph with many vertices that slowly evolves in time, as one link after another is inserted between two randomly selected nodes. However idealized, this model captured a combinatorial complexity of the real networks that are poorly connected at the inception and become more and more tight as more and more pairwise links appear in a chaotic fashion. Erdos and Renyi discovered a remarkable mathematical phenomenon: for a long time the evolving graph remains split in many small connected components, and then during a relatively short time period the graph undergoes a dramatic transition which results in the appearance of a giant connected subnetwork (subgraph) that contains a positive fraction of all vertices. This pioneering work started an avalanche of research aimed at elucidating deeper feautures of the phase transition phenomenon and tracking down the likely changes in the graph structure after the giant component has appeared. This research includes a detailed study of the group of largest components at the moments when they are about to merge into a giant component. Another component of this research is to have a close look at a core of the giant component, i.e. the largest subset of vertices in that component which are connected to each other noticeably stronger than to the other vertices. The principal investigator will work on alternative random graph models that may be closer to the real-life networks. One such network is the World Wide Web. There is a body of interesting, but not rigorous, research on the networks that grow population-wise in such a way that the most connected nodes are statistically preferred as contacts by the arrivals. The proposer plans to study these network growth processes jointly with D. Aldous and A. Frieze. Other classic examples of combinatorial structures are the partitions of sets and integers. And again there are numerous illustrations of how useful and insightful these abstractions are in applications. An integer partition is a partition of a given integer into decreasing parts. A central problem is to study the structure of a partition chosen at random among all such partitions. Since the pioneering work by Erdos and Lehner, the studies by Szalay, Turan, Fristedt and this investigator resulted in discovery of a rather detailed picture (shape) of the typical partition. The investigator plans to continue his research on the random integer partitions, and to extend it to the random plane partitions, a surprisingly rich combinatorial scheme, whose probabilistic aspects have only started to emerge. The investigator plans to combine enumerational tools and the probabilistic techniques in order to study the geometric characteristics of the typical plane partitions. The random partitions have been found critically important in probabilistic studies of optimization problems. One such well known problem is to partition a given set of numbers (weights) into two groups so that the weights of two groups are as close to each other as possible. Simplicity of this problem is deceiving: there is no efficient algorithm to solve it when the set of weights is large. It is natural then to switch attention and to study computational complexity of a typical problem when the individual weights are random. In on-going joint research C. Borgs, J. Chayes and the investigator have found a parameter of the problem whose value plays a crucial role in determination of how intrinsically difficult a typical instance of the problem is. Much as the partition problem differs from the evolving random graph, there is a striking similarity between two structures: both experience a rapid transition within a surprisingly narrow window on the parameter scale. The research will continue, and the collaborators plan to broaden it, to include various other optimization problems.

组合结构的一个典型示例是网络（图），被描述为通过链接（弧、边）连接到邻居的一组节点（顶点）。网络（图）长期以来一直被用作现实生活中的社交和技术网络的抽象数学描述。 1960 年，Erdos 和 Renyi 开始研究一种具有许多顶点的图的数学模型，随着时间的推移，一个接一个的链接被插入到两个随机选择的节点之间，该模型会缓慢演化。无论多么理想化，该模型都捕捉到了真实网络的组合复杂性，这些网络在开始时连接很差，并且随着越来越多的成对链接以混乱的方式出现而变得越来越紧密。 Erdos 和 Renyi 发现了一个显着的数学现象：在很长一段时间内，不断演化的图仍然分裂成许多小的连通分量，然后在相对较短的时间内，图经历了戏剧性的转变，导致出现一个巨大的连通子网（子图），其中包含所有顶点的正分数。这项开创性的工作开启了一系列研究，旨在阐明相变现象的更深层次特征，并追踪巨型组件出现后图结构可能发生的变化。这项研究包括对最大组件组即将合并成巨型组件时的详细研究。这项研究的另一个组成部分是仔细观察巨型组件的核心，即该组件中最大的顶点子集，它们之间的连接明显强于其他顶点。首席研究员将研究可能更接近现实生活网络的替代随机图模型。万维网就是这样的网络之一。有大量关于网络的有趣但不严格的研究，这些网络随着人口的增长而增长，在统计上，连接最紧密的节点在统计上被优先选择为到达者的联系人。提议者计划与 D. Aldous 和 A. Frieze 共同研究这些网络增长过程。组合结构的其他经典示例是集合和整数的划分。同样，有大量的例子说明了这些抽象在应用程序中是多么有用和富有洞察力。整数分区是将给定整数划分为递减的部分。一个中心问题是研究所有此类分区中随机选择的分区的结构。自 Erdos 和 Lehner 的开创性工作以来，Szalay、Turan、Fristedt 和本研究人员的研究发现了典型分区的相当详细的图片（形状）。研究人员计划继续他对随机整数分区的研究，并将其扩展到随机平面分区，这是一种令人惊讶的丰富组合方案，其概率方面才刚刚开始出现。研究人员计划结合枚举工具和概率技术来研究典型平面分区的几何特征。人们发现随机划分在优化问题的概率研究中至关重要。一个众所周知的问题是将一组给定的数字（权重）分为两组，以使两组的权重尽可能接近。这个问题的简单性是具有欺骗性的：当权重集很大时，没有有效的算法来解决它。当各个权重是随机的时，转移注意力并研究典型问题的计算复杂性是很自然的。在正在进行的联合研究中，C. Borgs、J. Chayes 和研究人员发现了问题的一个参数，其值在确定问题的典型实例本质上有多困难方面起着至关重要的作用。尽管划分问题与演化的随机图不同，但两种结构之间存在惊人的相似性：两者都在参数尺度上令人惊讶的狭窄窗口内经历了快速转变。该研究将继续进行，合作者计划扩大研究范围，以包括各种其他优化问题。