图的极限及其动力学行为

In recent years, based on the needs of communication, biological science and material sciences, etc., the research of huge networks becomes an important and hot topic in modern science and technology. Huge networks have two remarkable features: huge and dynamic. In order to study this kind of networks, mathematicians propose concepts of graph sequence and graph limit. Professor Lovasz, once the president of the international union of mathematicians, recently published a book on this topic: Large Networks and Graph Limits. On the other hand, many outstanding scholars in graph theory, such as Bollabas, Biggs and Babai, all have studied the dynamic behavior of graphs. This project is concentrated to the following aspects: two most basic dynamic processes on graphs-random walk and Abelian sandpile model; the asymptotic behavior of various kinds of parameters on graph sequences. We wish to enrich and develop theories and methodologies of graph theory, explore the relations between graph theory and modern dynamic theory, and provide new ideas for complex system analysis.

近年来，基于通讯，生物科学，材料科学等的需要，大型网络的研究成为当代科学技术的重要热点。大型网络的特点：一是规模巨大；二是动态的。为了研究这种网络，数学家提出了图序列与图极限的概念，曾任国际数学家联盟主席 Lovasz 教授最近出版了这方面的第一本专著：Large Networks and Graph Limits。另一方面Bollabas，Biggs，Babai等一大批图论界顶尖学者都研究过图的动力学行为，如图上的随机游动，Abelian沙堆模型等。在此基础上本项目研究动态图序列上的两种最基本的动态过程：图上的随机游动和Abelian沙堆模型，并考察不同图序列上图的各种参数的渐近行为以及它们与图结构之间的关系。本项目的研究希望能丰富和发展图论的理论体系和方法，探索它与当代动力系统理论间的联系，并为复杂网络分析提供新的思路。

本项目研究两方面的内容：一是研究给定的图集合或图序列上某个参数的分布情况或极限行为；二是研究图上的两个随机过程-随机游动和 Abelian 沙堆模型-的动力学行为。这些对了解大规模的离散复杂系统内部进化机制和变化趋势都有非常重要的意义。 本项目主要研究了下面三方面的内容： . 1. 研究了无圈分子图的HOMO-LUMO指标的分布情况，确定了其所有的极限点。并研究了和图上随机游动相关的各种参数（如：规范化的拉普拉斯谱，等效电阻等）在图的各种运算下的变化规律，以及其极限行为。这方面的成果已分别发表在Physica A、Applied Mathematics and Computation与MATCH Commun. Math. Comput. Chem.等期刊上。. 2. 研究 Abelian 沙堆模型达到稳定时所有常返构型所构成的沙堆群 (临界群）和图的结构之间的关系。 尝试充分利用图自身的结构尽可能的减少沙堆群生成元的个数，从而使其关系矩阵的阶数远远小于常用的关系矩阵-约化的拉普拉斯矩阵，从而完全确定沙堆群的结构。这为研究平面图，甚至更广的串并联图的沙堆群提供了新的研究思路。这方面的部分成果已正式发表在Discrete Applied Mathematics和Bull. Malays. Math. Sci. Soc.等期刊上。. 3. 提出了一个全新的图多项式-平均拉普拉斯多项式，并研究这个多项式和其它多项式之间的关系以及其系数的组合意义。所得结果已发表在 Discrete Applied Mathematics 上。