Ramanujan Graphs
Ramanujan Graphs
复制标题
拉马努金图
DOI：
10.1090/amsip/007/08
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
A. Pizer
中科院分区：
文献类型：
--
作者：
A. Pizer
本文的目的是给出一大类Ra-manujan图的显式构造。Ramanujan图G是有限连通的FC-正则图，具有G的邻接矩阵的最大非平凡特征值在渐近意义下尽可能小的性质。下文第3节给出了准确的定义。特征值界迫使这类图具有高的“放大率”(或当它们是二部图时的“扩展”)，因此它们在网络的构建和显式算法中有许多应用。直观地说，它们是稀疏图(在某种意义上，它们的边很少)，具有顶点的子集总是有许多不同的邻居的属性。除了拉马努扬之外，我们构建的曲线图也有很大的周长。Ramanujan图的第一个构造是由Lubotzky，Phillips和Sarnak[LPS86，LPS88]和Marguis[Mar88]独立给出的。Bien[Bie89]写了一篇关于这个主题的很好的调查文章。我们的构造是基于四元数代数的算术，并依赖于Hecke算子和模形式的理论。在给出第4节和第5节的构造之前，我们在第2节发展了图论的一些结果，并在第3节讨论了一般Ramanujan图。很高兴在Oliver Atkin退休之际将这篇关于Ramanujan图的论文献给Oliver Atkin。阿特金对这一领域的贡献在下面定理5.2之前的示意图中得到了解释。
The purpose of this paper is to give an explicit construction of a large class of Ra manujan graphs. A Ramanujan graph G is a finite, connected, fc-regular graph with the property that the largest nontrivial eigenvalue of the adjacency matrix of G is as small as possible in an asymptotic sense. The precise definition is given in section 3 below. The eigenvalue bound forces such graphs to have high “magnification” (or “expansion” when they are bipartite) and as such they have many applications to the construction of networks and explicit algorithms. Intuitively, they are sparse graphs (in the sense that they have few edges) with the property that subsets of vertices always have many distinct neighbors. In addition to being Ramanujan, the graphs we con struct also have large girth. The first constructions of Ramanujan graphs were given by Lubotzky, Phillips, and Sarnak [LPS86, LPS88] and independently by Margulis [Mar88]. Bien [Bie89] has written an excellent survey article on the subject. Our con struction is based on the arithmetic of quaternion algebras and depends on the theory of Hecke operators and modular forms. Before giving the construction in sections 4 and 5, we develop some results on graph theory in section 2 and discuss general Ramanujan graphs in section 3. It is a pleasure to dedicate this paper on Ramanujan Graphs to Oliver Atkin on the occasion of his retirement. Atkin’s contribution to this area is explained in the peiragraph preceding Theorem 5.2 below.