Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
复制标题
随机凯莱图和顶点传递图通过矩阵鞅的展开性质
DOI：
10.1002/rsa.20177
复制
发表时间：
2007
影响因子：
1
通讯作者：
Christofides D
中科院分区：
文献类型：
--
作者：
Christofides D
Alon-Roichman定理指出，对于每一个ε> 0，存在一个常数（ε），使得一个有限群G关于G的c(ε)log∣G∣元素的Cayley图，独立且均匀随机选择，期望第二大特征值小于ε。特别地，这样的图是一个具有高概率的展开器。朗道和罗素，以及卢和舒尔曼各自改进了定理的边界。继朗道和罗素之后，我们给出了一个新的证明，进一步改进了边界。当考虑一般群pg时，我们的界在某种意义上是最佳可能的。我们还将Alon-Roichman定理推广到随机协集图。对于算子值随机变量，我们的证明使用了Hoeffding‐类型的结果，我们相信这是一个独立的兴趣。©2007 Wiley期刊公司随机结构。Alg。, 2008年
The Alon–Roichman theorem states that for every ε> 0 there is a constantc(ε), such that the Cayley graph of a finite groupGwith respect toc(ε)log ∣G∣ elements ofG, chosen independently and uniformly at random, has expected second largest eigenvalue less than ε. In particular, such a graph is an expander with high probability.Landau and Russell, and independently Loh and Schulman, improved the bounds of the theorem. Following Landau and Russell we give a new proof of the result, improving the bounds even further. When considered for a general groupG, our bounds are in a sense best possible. We also give a generalization of the Alon–Roichman theorem to random coset graphs.Our proof uses a Hoeffding‐type result for operator valued random variables, which we believe can be of independent interest. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008