Loading...
conference paper
Some graph products and their expansion properties
2006
Proceedings of the IEEE Information Theory Workshop, 2006
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.
Type
conference paper
Web of Science ID
WOS:000245205900036
Authors
Publication date
2006
Published in
Proceedings of the IEEE Information Theory Workshop, 2006
Start page
170
End page
174
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
January 16, 2007
Use this identifier to reference this record