随机有向图的特征值和随机图的划分

Random graphs have been the focal point of graph theory for a long time. In recent years, eigenvalues of random graphs, bipartite decomposition of random graphs and their related questions have attracted a lot of researchers' attention, for example, the famous combinatorists Noga Alon, Fan Chung, and Van Vu etc. For this project, we aim to apply the combinatorial probabilistic methods together with techniques from random matrix theory and extremal graph theory to study problems that include eigenvalues of the normalized Laplacian matrix of random directed graphs, bipartite decomposition of random graphs and a corresponding problem for random hypergraphs. The investigation of problems drafted above will make contributions to the development of the random graph theory.

关于随机图的研究是当今图论前沿方向之一。近些年来，随机图的特征值问题，随机图的完全二部图划分问题以及相关问题受到很大关注。从事过这方面研究的著名组合学家包括 Noga Alon、Fan Chung、Van Vu等。本项目旨在运用概率方法并结合其他的一些方法，比如随机矩阵和极值图论中的方法，来研究随机有向图的规范拉普拉斯特征值问题，随机图的完全二部图划分问题以及相对应的随机超图的划分问题。这些问题的探讨将会丰富随机图论的研究。

图的完全二部图划分问题由Graham和Pollak引入。Erdős对随机图的完全二部图划分问题的猜想最近受到很多研究。我们可以类似定义超图的子超图划分问题。Alon等研究过超图的该划分问题。按照本项目的计划，我们研究了随机超图的子超图划分问题，建立了该问题和完全超图的图兰密度之间的联系。. 图和有向图相关矩阵的特征值可以用来刻画图和有向图的结构性质。在研究随机图有向图的特征值过程中，我们发现图的特征值和图的哈密尔顿性以及图的Randić指标之间的联系，并进行了相应的研究。