凯莱图的谱间隙与扩展属性研究

Cayley graphs, as the regular graphs defined by groups and their subsets, build the important bridges between graph theory, group theory, representation theory and combinational design theory. An expander family is defined as the infinite family of regular graphs with fixed degree whose expansion constants are bounded away from zero. The widespread application of expander families in computer science and pure mathematics makes the problem of constructing such families become an important problem paid attention by a group of mathematicians all around the world. Expander families are usually sparse and highly connected, which requires that the construction model should have better symmetry and uniformity. Cayley graphs can always meet these requirements, and their spectral gap are strongly related to the expansion constant, thus determining or estimating the spectral gap of Cayley graphs are crucial for constructing expander families...In this project, starting from equitable partitions and quotient matrices of graphs, and using matrix theory, representation theory and group theory as main tools, we study on the spectral gap and expansion properties of Cayley graphs on transitive groups. The details include two aspects: firstly, we consider the problem of determining or estimating the spectral gap of Cayley graphs on transitive groups, and particularly, we will determine the spectral gap of normal Cayley graphs and important network Cayley graphs on some transitive permutation groups; secondly, we consider the problem of constructing or characterizing expander Cayley families on transitive groups, and in particular, we will characterize the Ramanujan Cayley graphs on some transitive permutation groups.

凯莱图，作为由群及其子集定义的正则图，是连接图论、群论、表示论和组合设计理论的重要桥梁。扩展图类是指扩展常数具有一致非零下界的常度数正则图的无穷类。扩展图类在计算机科学和纯粹数学中的广泛应用，使得其构造问题成为国际上一批数学家关注的重要问题。扩展图类通常是稀疏和高度连通的，这要求其构造模型具有较好的对称性和均匀性。凯莱图往往可以满足这些要求，且其谱间隙与扩展常数密切相关，因此确定或估计凯莱图的谱间隙对于扩展图类的构造至关重要。..本项目从图的公平划分与商矩阵出发，以矩阵论、表示论和群论为主要工具，对传递群上凯莱图的谱间隙与扩展属性展开研究。具体内容包括两个方面：一是研究传递群上凯莱图的谱间隙的确定或估计问题，特别要确定某些传递置换群上的正规凯莱图及重要网络凯莱图的谱间隙；二是研究传递群上扩展凯莱图类的构造或刻画问题，特别要刻画某些传递置换群上的拉马努金凯莱图。

代数图论是图论的重要研究领域之一，主要研究的是如何利用代数方法来解决图论问题。凯莱图是代数图论的重要研究对象，这类图与群的抽象结构密切相关，并且是构造扩展图类的理想模型。由于凯莱图的谱间隙与扩展常数之间有着紧密的联系，研究凯莱图的谱间隙对于扩展图类的构造有着重要意义。在本项目中，我们研究了高度传递群上凯莱图的谱间隙的确定问题，给出了确定高度传递群上正规凯莱图的谱间隙的递归方法，并利用该方法确定了对称群上支撑数不超过5的大部分正规凯莱图和交错群上几类重要凯莱图的谱间隙。此外，我们还研究了距离正则凯莱图的刻画问题以及谱极值图论中的相关问题，取得的主要结果有：1) 给出了双环群上距离正则凯莱图的完整分类，并刻画了广义双环群上的所有极小距离正则凯莱图；2) 确定了不含轮图、友谊图等图作为子图的图的最大邻接谱半径或无符号拉普拉斯谱半径；3) 证明了 Estrada 教授提出的关于图的CDS指标的极值猜想；4) 利用规范化拉普拉斯特征值给出了一般图的坚韧度的下界；5) 确定了第二大无符号拉普拉斯特征值不超过5的恰有三个不同无符号拉普拉斯特征值的图。.