论文标题
用于功率图和广义Ramanujan图的Alon-Boppana定理
An Alon-Boppana theorem for powered graphs and generalized Ramanujan graphs
论文作者
论文摘要
图的第r-th幂通过连接距离r中的每个顶点对来修改图形。本文对图形的第三幂（包括不规则图）进行了Alon-Boppana定理的概括。这导致了Ramanujan图的广义概念，该图的频谱差距与派生的Alon-Boppana结合匹配。特别是，我们表明某些由于局部不规则性而不是良好扩展器的图形，例如erdos-renyi随机图，几乎曾经启动过ramanujan。 Ramanujan图的不同概括也可以从非背带操作员获得。接下来，我们认为，动力操作员给出了比后者更强大的概念：稀疏的erdos-renyi随机图和对手修改log（n）^c $ pertices的子图几乎仍然是ramanujan的，但在非背后的意义上并不是Ramanujan。作为应用程序，这为不同的块模型提供了强大的社区测试。
The r-th power of a graph modifies a graph by connecting every vertex pair within distance r. This paper gives a generalization of the Alon-Boppana Theorem for the r-th power of graphs, including irregular graphs. This leads to a generalized notion of Ramanujan graphs, those for which the powered graph has a spectral gap matching the derived Alon-Boppana bound. In particular, we show that certain graphs that are not good expanders due to local irregularities, such as Erdos-Renyi random graphs, become almost Ramanujan once powered. A different generalization of Ramanujan graphs can also be obtained from the nonbacktracking operator. We next argue that the powering operator gives a more robust notion than the latter: Sparse Erdos-Renyi random graphs with an adversary modifying a subgraph of log(n)^c$ vertices are still almost Ramanujan in the powered sense, but not in the nonbacktracking sense. As an application, this gives robust community testing for different block models.
