Relative expanders or weakly relatively Ramanujan graphs
Relative expanders or weakly relatively Ramanujan graphs
复制标题
相对展开图或弱相对拉马努金图
DOI：
10.1215/s0012-7094-03-11812-8
复制
发表时间：
2003
影响因子：
2.5
通讯作者：
J. Friedman
中科院分区：
文献类型：
--
作者：
J. Friedman
令G为最大（邻接矩阵）特征值0的XED图，其通用覆盖率具有光谱半径。这给出了具有\ small“特征值的某些树的列者，只要我们忽略了\ old''eigenvalues与Lubotzkynagnibeda的负面结果相反，这表明有一棵树，所有其黑nite商都不是\ Ramanujan，“从Lubotzky-Philips-Sarnak和Greenberg的意义上讲。我们的主要结果是\相对版本的“ Broder-Shamir绑定在随机常规图的特征值上。它们的某些组合技术被g.f的通用封面上的光谱技术取代，或者在G.F的通用封面上或将我们的定理专门为G.F的选择替换为Brodershamir设置，我们的结果略有改善。
Let G be a xed graph with largest (adjacency matrix) eigenvalue 0 and with its universal cover having spectral radius .W e show that a random cover of large degree over G has its \new" eigenvalues bounded in absolute value by roughly p 0. This gives a positive result about nite quotients of certain trees having \small" eigenvalues, provided we ignore the \old" eigenvalues. This positive result contrasts with the negative result of LubotzkyNagnibeda that showed that there is a tree all of whose nite quotients are not \Ramanujan" in the sense of Lubotzky-Philips-Sarnak and Greenberg. Our main result is a \relative version" of the Broder-Shamir bound on eigenvalues of random regular graphs. Some of their combinatorial techniques are replaced by spectral techniques on the universal cover of G .F or the choice ofG that specializes our theorem to the BroderShamir setting, our result slightly improves theirs.