I was wondering how to relate the spectra of the Zig-Zag product of two graphs in term of the factors...someone can help me?
2
-
$\begingroup$ What is the definition of the Zig-Zag product? $\endgroup$– Richard StanleyCommented Sep 10, 2016 at 13:43
-
$\begingroup$ @RichardStanley See the wikipedia article, or the actual article cited in my answer. $\endgroup$– Igor RivinCommented Sep 10, 2016 at 17:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The spectral gap is analyzed in the foundational paper I don't know if you can say anything else.
Omer Reingold, Salil Vadhan, and Avi Wigderson, MR 1888797 Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. of Math. (2) 155 (2002), no. 1, 157--187.
answered Sep 10, 2016 at 17:54