Lifts, Discrepancy and Nearly Optimal Spectral Gaps
Lifts, Discrepancy and Nearly Optimal Spectral Gaps
复制标题
提升、差异和接近最佳的光谱间隙
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
N. Linial
中科院分区：
文献类型：
--
作者：
Yonatan Bilu;N. Linial
设G是具有n个顶点的图。图G的2-提升是2n个顶点的图H，有一个覆盖映射�：H→G。不难看出，G的所有特征值也是H的特征值。此外，H有n个“新的”特征值。我们猜想每个d-正则图都有一个2升程，使得所有新的特征值都在[−2√d−1，2√d−1]的范围内(如果是真的，这是紧的，例如按Alon-Boppana界)。这里我们证明了每个最大度d的图都有一个2-提升使得所有的
Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map � : H → G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2lift such that all new eigenvalues are in the range [−2 √ d − 1,2 √ d − 1] (If true, this is tight , e.g. by the Alon-Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all