极值图论的随机结构和概率方法

Since other researches such as network sciences have apllied more and more results from the graph theory, and the graph theory particularly the extremal graph theory has been focused more than ever before. The extremal graph theory such as Ramsey theory reveals the complexity of graphs and networks. The random structures behind them extend our knowledge. This project aims on probabilistic methods and random structures in extremal graph theory and devotes ourselves to topics such as estimating asymptotic behavior of Ramsey functions and developing some current new methods. In particular, for some problems, we shall establish quasi-random graphs such that probabilistic methods can be applied to obtain new results. Besides, behind social networks and big data, the backgrouds are often random graphs. Some most famous papers on social networks studied the properties between complete random graphs and regular graphs. The applicants should help young students to be familiar with these topics and methods.

随着其他学科如网络科学对图论的应用，近年来图论的研究得到很大的提升，其中极值图论受到了空前的关注。由于极值图论特别是Ramsey理论，揭示了图（网络）的复杂性，其背后的随机结构拓宽了人们对有限结构的认识。本项目着眼于极值图论中的概率方法和随机结构，致力于一些重要的课题，例如Ramsey函数的渐进估计，发展和使用一些国际上颇受重视的方法。特别地，对于特定的问题，我们试图得到具有拟随机性的构造，从而使用概率方法，改进或者获得一些新的成果。此外，不少社会网络和大数据研究的背后，也都具有随机结构的背景，几篇最著名的社会网络的论文，都是研究社会网络介于完全随机图和完全正则图之间的特性，这是随机图理论在近些年的一个热点应用。本课题组也试图在网络的研究上获得一些有价值的理论成果，且尽可能在概率方法的普及上做出一些应有的贡献。

图的Ramsey理论是极值图论最重要的方向，理论性强，难度大，是一些重要图论工具的诞生地，也是图论现代化的标记。其中，随机图论的诞生，被认为是图论革命性事件。现在正在被众多学者研究的随机算法，也是由于随机图的大力推动。本项目致力于研究极值图论的随机结构和概率方法，主要着眼于图的Ramsey理论的极值结构和概率方法，取得了一系列成果。我们给出一些Ramsey-Turan数的结果，证明在边密度较小（甚至趋于零）时，在阶数大致为Ramsey数的随机图中，几乎所有的图满足性质：其边任何红蓝着色都包含单色的给定图。这些结果暗示在阶为确切Ramsey数的完全图中，也可以删去一些给定的图，使之依旧具有Ramsey性质。从而我们定义这类被删去的子图最大阶为Ramsey surplues number. 我们在这些方面取得了一些成果，发表了二十多篇论文，在Springer出版专著一本。