图的生成树计数、临界群及其相关问题研究

The problem on enumeration of spanning trees of graphs was first found by the physicist Kirchhoff during considering electronic networks. This problem is closely related to the q-state Potts model and reliable networks design. It is also one of the most elementary problems in algebraic graph theory. The critical group of graphs is closely related to either arithmetical geometry and algebraic geometry or the sandpile model in statistical physics and Chip-Firing Games in algebraic graph theory. Since the order of the critical group of a graph equals its number of spanning trees, its invariant factor is the refinement of the number of spanning trees. Hence it can be regarded as an isomorphic invariant and is closely related to the problem on enumeration of spanning trees. This project will investigate the following problems: (1). The problem on enumeration of spanning trees of graphs embedded on surfaces, particularly, the relations between the numbers of spanning trees of lattices and their dual lattices on the torus in the context of statistical physics. (2). Relations between the numbers of spanning trees of a general graph and its various transformation graphs, particularly, between the numbers of spanning trees of an irregular graph and its line graph. (3). The theory on the critical group of graphs, especially, the relation between other structure parameters of a graph and its critical group. (4). Relations among above three problems and applications.

图生成树的计数问题首先由物理学家基尔霍夫在分析电网络时发现，与统计物理中的q-状态Potts模型及网络的可靠性设计密切相关，是代数图论中研究的最基本问题之一。图的临界群不但与算术几何、代数几何有关，也与统计物理中的沙堆模型以及代数图论中的Chip-Firing Games有紧密联系。由于临界群的阶等于图的生成树数目，它的不变因子是图生成树数目的一个加细, 因此可以看做图的一个精细同构不变量，与图的生成树的计数问题密切相关。本项目主要研究以下问题：(1) 嵌入在曲面上的图及其对偶图的生成树的计数问题，重点为统计物理背景下嵌入在环面上的格子图及其对偶图的生成树数目之间的关系。(2) 一般图及其各种变换图的生成树数目之间的关系，特别是非正则图及其线图的生成树数目之间的内在关系。(3) 图的临界群理论，探讨图的其它结构参数和临界群之间的关系。(4) 以上三个问题之间的内在联系及其应用。

图生成树的计数问题与统计物理中的q-状态Potts模型及网络的可靠性设计密切相关，是代数图论中研究的最基本问题之一。图的临界群不但与算术几何、代数几何有关，也与统计物理中的沙堆模型以及代数图论中Chip-Firing Games有紧密联系。本项目主要研究了以下问题：.(1) 一般图及其各种变换图的生成树数目之间的关系，特别是非正则图及其线图的生成树数目之间的内在关系。包括，一般图与其线图（Line Graph）的生成树数目之间的关系，一般图与其中间图（Middle Graphs）的生成树数目之间的关系。这些结果发表在Journal of Graph Theory等期刊上。.(2) 嵌入在环面上的Cairo Pentagonal Lattice、Generalized Union Jack Latttice等格子图及其环面对偶图的生成树的计数问题，也研.究了一类可二分网络（2-separable Networks）的计数问题，这些问题是近年来统计物理的热门研究对象。这些结果分别发表在J.Statis- tical Physics、Physica A等期刊上。.(3)研究了一些图的临界群理论，主要研究了一类所谓的多边形花（Polygon Flower）的临界群，完全刻画了这类图的临界群的结构。这些结果发表在Discrete Applied Mathematics上。.(4) 我们还研究了与以上问题密切相关的电网络中两点之间的电阻的计算问题。得到了包括几乎完全二部图网络、一类环形网络与路形网络、Sierpinski Gasket网络等中两点之间电阻的计算公式。这些结果分别发表在American Mathematical Monthly、Discrete Applied Mathematics、Journal of Statistical Physics等期刊上。