Mathematical Sciences: Random Graphs

首席研究员将研究随机演化图的巨大分量的顶点和边的连通性。Erdos-Renyi随机进化图的一个方面是，在平均顶点度等于1的时刻之后，巨大分量突然出现。本研究将有助于更好地理解随机图的色数、独立数和匹配数等重要极值特征的可能行为。研究者还将研究另外两个模型中的巨组分现象，二部随机图和聚合过程的Flory-Stockmayer-Whittle模型。最后，研究者将研究汉密尔顿电路和匹配的快速概率算法。

The principal investigator will study the vertex and edge connectivity of the giant component of a randomly evolving graph. One aspect of an Erdos-Renyi randomly evolving graph is a sudden appearance of the giant component, right after the moment when the average vertex degree becomes equal to 1. This research will lead to a better understanding of the likely behavior of such important extremal characteristics of the random graph as the chromatic number, the independence number and the matching number. The investigator will also study the giant component phenomenon in two other models, bipartite random graph and a Flory-Stockmayer-Whittle model of polymerization process. Finally, the investigator will work on fast probabilistic algorithms for Hamilton circuits and matchings.