Random Combinatorial Structures

大约在1960年，鄂尔多斯和仁义对他们所说的随机演化(重)图进行了系统的研究。从n个顶点上的空图开始，在每个离散时刻添加一条新的边，其位置在Re备选方案中随机地均匀地选择。基本的问题是，插入m条边后，随机图是什么样子的？他们能够对这个演化的图给出一个非常简洁的渐近描述，并打开了对这个过程和许多其他随机图过程的大量研究的大门。今天，随机图理论是概率组合学的一个蓬勃发展的领域，它在统计物理(渗流)、物理化学和理论计算机科学中得到了许多应用。值得注意的是，在分析不断增长的信息(社会)网络的概率模型时，随机图模型已变得不可或缺。作者将继续他在随机图(网络)模型上的工作，在该模型中，新的边(链接)倾向于加入更多的“社会”顶点(节点)，即那些具有比已有链接的平均数量更高的顶点(节点)。然而，这类图的简单数学模型有可能成为现实网络统计分析中有用的定量工具，而且它们在其他领域也被证明是有价值的，例如聚合理论。该建议还包括其他类型的随机图的问题，如每条边都有方向的有向图、纽结理论中的关键概念--弦图、分配权重且边仅在总权超过阈值的节点之间发展的阈值图、以及每个顶点度超过3的随机图(后一条件基本上是随机图有哈密尔顿圈的必要条件)。他还将使用具有约束度的随机图来分析随机布尔方程组的可解性。这个问题属于组合概率和理论计算机科学的一个迅速发展的领域，事实证明，它已经被证明接受了惊人的多样化的方法，包括统计物理的模型和方法。这项研究可能有助于理论模型和数学技术的发展，这些理论模型和数学技术可以被不同领域的研究人员使用，他们面临着基于关于单个节点之间的局部(成对)相互作用规则的假设来描述(预测)巨大网络的结构行为的挑战。申请人将利用这一研究项目来吸引研究生，并指导他们完成博士学位的学习。

Around 1960 Erdos and Renyi undertook a systematic study of what they called a randomly evolving (re) graph. Starting with an empty graph on n vertices, at each discrete moment a new edge is added, its position being chosen uniformly at random among the re alternatives. The basic question is what does the random graph look like after some m edges have been inserted? They were able to give a remarkable concise asymptotic description of this evolving graph, and opened the gates to a flood of research on this and many other random graph processes. Today random graph theory is a thriving area of probabilistic combinatorics that has found many applications in statistical physics (percolation), physical chemistry and theoretical computer science. Quite remarkably, random graph models have become indispensable for the analysis of probabilistic models of growing information (social) networks. The proposer will continue his work on a model of random graph (network) in which the new edges (links) tend to join the more "social" vertices (nodes), those with higher than average number of already existing links. However simple-minded, mathematical models of such graphs have a potential to become useful quantitative tools in the statistical analysis of real-life networks and they have proved to be valuable in other areas, such as polymerization theory. The proposal includes problems on other classes of random graphs, such as directed graphs in which each edge has a direction, chordal diagrams--a key notion in knot theory, threshold graphs in which the nodes are assigned weights and the edges develop only between the nodes with the total weight exceeding a threshold value, and random graphs in which each vertex degree exceeds 3. (The latter condition is basically necessary for the random graph to have a Hamilton cycle.) He will also use random graphs with restricted degrees to analyze solvability of a random system of Boolean equations. This problem belongs to a rapidly developing area of combinatorial probability and theoretical computer science that has turned out to be receptive to strikingly diverse approaches, including models and methods of statistical physics.This research may contribute to development of theoretical models and mathematical techniques that can be used by researchers in various areas who confront a challenge to describe (to predict) the structural behavior of huge networks based on assumptions regarding rules of local (pairwise) interactions between the individual nodes. The proposer will use this research program to engage his graduate students and to guide their studies toward completion of their PhD degrees.