The Zig-Zag Graph Product, and Elementary Construction of
Expander Graphs.
Omer Reingold, AT&T Research and Institute for Advanced Study
October 10, 4:30 PM, Rutgers Univ. CORE building Room 430
Abstract.
Expander graphs are combinatorial objects which are fascinating and
useful, but seemed hard to construct. The main result we present is an
elementary way of constructing them.
The essential ingredient is a new type of graph product, which we call
the zig-zag product. Taking a product of a large graph with a small
graph, the resulting graph inherits (roughly) its size from the large
one, its degree from the small one, and its expansion properties from
both! Iteration yields simple explicit constructions of constant-degree
expanders of arbitrary size, starting from one constant-size expander.
Crucial to our intuition (and simple analysis) of the properties of
this graph product is the view of expanders as functions which act as
``entropy wave'' propagators --- they transform probability
distributions in which entropy is concentrated in one area to
distributions where that concentration is dissipated. In these terms,
the graph product affords the constructive interference of two such
waves.
No special background is assumed. Joint work with Salil Vadhan and Avi
Wigderson.
Back to
Discrete Math/Theory of Computing seminar