Theory Seminar: A combinatorial construction of almost-Ramanujan graphs using the
zig-zag product

Avraham Ben-Aroya (Tel-Aviv Univ.)

Sunday, 06.04.2008, 11:00

Room 337-8 Taub Bld.

Reingold, Vadhan and Wigderson [FOCS'00] introduced the graph zig-zag
product. This product combines a large graph and a small graph into one
graph, such that the resulting graph inherits its size from the large graph,
its degree from the small graph and its spectral gap from both. Using this
product they gave the first fully-explicit combinatorial construction of
expander graphs. They showed how to construct $D$-regular graphs having
spectral gap $1-O(D^{-\frac{1}{3}})$. In the same paper, they posed the open
problem of whether a similar graph product could be used to achieve the
almost-optimal spectral gap $1-O(D^{-\frac{1}{2}})$.

In this paper we propose a generalization of the zig-zag product that combines a large graph and several small graphs. The new product gives a better relation between the degree and the spectral gap of the resulting graph. We use the new product to give a fully-explicit combinatorial construction of $D$-regular graphs having spectral gap $1-D^{-\frac{1}{2} + o(1)}$.

Joint work with Amnon Ta-Shma

In this paper we propose a generalization of the zig-zag product that combines a large graph and several small graphs. The new product gives a better relation between the degree and the spectral gap of the resulting graph. We use the new product to give a fully-explicit combinatorial construction of $D$-regular graphs having spectral gap $1-D^{-\frac{1}{2} + o(1)}$.

Joint work with Amnon Ta-Shma