The Spectral Gap of a Random Subgraph of a Graph
The Spectral Gap of a Random Subgraph of a Graph
复制标题
图的随机子图的谱间隙
作者：
F. C. Graham;P. Horn
本文研究了图G和它的随机子图之间的关系，这些随机子图是由每个边以概率p独立选择而定义的.假设G有一个谱间隙λ（以它的归一化Laplacian表示）和最小度d min，那么我们可以证明G的一个n阶随机子图的边选择概率p几乎必然有λ作为它的谱间隙.
We examine the relationship of a graph G and its random subgraphs, which are defined by independently choosing each edge with probability p. Suppose that G has a spectral gap λ (in terms of its normalized Laplacian) and minimum degree d min. Then we can show that a random subgraph of G on n vertices with edge-selection probability p almost surely has as its spectral gap .