Entropy waves, the zig-zag graph product, and new constant-degree expanders (Q1613289): Difference between revisions

Let \(G_1\) be a \(|D|\)-regular graph on the vertex set \(X\) and \(G_2\) a regular graph on the vertex set \(D\). The authors define the so-called zig-zag product of \(G_1\) and \(G_2\) on the vertex set \(X\times D\) and the adjacency relation defined in a complicated way. An upper bound for the second largest eigenvalue (in absolute value) of the zig-zag product of \(G_1\) and \(G_2\) is obtained. This enables the construction of an infinite family of expanders.