Some graph products and their expansion properties

被引：0
|
作者：
Brown, Andrew [1 ]
Shokrollahi, Amin [1 ]
机构：
[1] Ecole Polytech Fed Lausanne, CH-1015 Lausanne, Switzerland
来源：
2006 IEEE INFORMATION THEORY WORKSHOP | 2006年
关键词：
D O I：
10.1109/ITW.2006.1633804
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We introduce "derandomized" versions of the tensor product and the zig-zag product, extending the ideas in the derandomized squaring operation of Rozenman and Vadhan. These enable us to obtain graphs with smaller degrees than those obtained using their non-derandomized counterparts, though at the cost of slightly worse expansion. In this paper we give bounds on these expansions (measured by their second eigenvalues), and also obtain an improved bound on the expansion of the derandomized square.
引用
收藏
页码：170 / +
页数：2
相关论文
共 50 条
12345