Spectra of lifted Ramanujan graphs
Spectra of lifted Ramanujan graphs
复制标题
提升拉马努金图的光谱
DOI：
10.1016/j.aim.2011.03.016
复制
发表时间：
2009
影响因子：
1.7
通讯作者：
V. Vu
中科院分区：
文献类型：
--
作者：
E. Lubetzky;B. Sudakov;V. Vu
一个基图G的随机n-提升是它在顶点[n]× V（G）上的覆盖图H，其中对G中的每条边uv都有一个独立的一致双射π，且H的所有边都具有（i，u），（π（i），v）的形式.研究升降机的一个主要动机是理解拉马努金图，即这样的图的典型覆盖是否也是拉马努金。设G是一个具有最大特征值λ 1的图，ρ是它的泛覆盖的谱半径. Friedman（2003）[1/2]证明了G的随机提升的每一个“新”特征值都以很高的概率为O（ρ 1/2 λ 1 1/2），并给出了ρ+ o（1）的一个界，该界比Lubotzky和Greenberg（1995）[15]的结果更紧。Linial和Puder（2010）[17]改进了Friedman的O（ρ 2/3 λ 1 1/3）约束。对于d-正则图，其中λ 1= d且ρ= 2 d− 1，这转化为O（d 2/3）的界，而不是限制的2 d− 1。本文分析了d-正则图的随机n-提升的谱，其非平凡特征值的绝对值都不超过λ。我们证明了提升的每个非平凡特征值的绝对值以很高的概率为O（（λ <$ρ）log ρ）.这个结果紧到一个对数因子，并且对于λ d 2/3− ε，它实质上改进了弗里德曼和Linial和Puder的上界。特别是，它意味着一个典型的拉马努金图的n-提升几乎是拉马努金。
A random n-lift of a base-graph G is its cover graph H on the vertices [n]× V (G), where for each edge uv in G there is an independent uniform bijection π, and H has all edges of the form (i, u),(π (i), v). A main motivation for studying lifts is understanding Ramanujan graphs, and namely whether typical covers of such a graph are also Ramanujan. Let G be a graph with largest eigenvalue λ 1 and let ρ be the spectral radius of its universal cover. Friedman (2003)[12] proved that every “new” eigenvalue of a random lift of G is O (ρ 1/2 λ 1 1/2) with high probability, and conjectured a bound of ρ+ o (1), which would be tight by results of Lubotzky and Greenberg (1995)[15]. Linial and Puder (2010)[17] improved Friedmanʼs bound to O (ρ 2/3 λ 1 1/3). For d-regular graphs, where λ 1= d and ρ= 2 d− 1, this translates to a bound of O (d 2/3), compared to the conjectured 2 d− 1. Here we analyze the spectrum of a random n-lift of a d-regular graph whose nontrivial eigenvalues are all at most λ in absolute value. We show that with high probability the absolute value of every nontrivial eigenvalue of the lift is O ((λ∨ ρ) log ρ). This result is tight up to a logarithmic factor, and for λ⩽ d 2/3− ε it substantially improves the above upper bounds of Friedman and of Linial and Puder. In particular, it implies that a typical n-lift of a Ramanujan graph is nearly Ramanujan.