
In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the zig-zag product of
regular graph
In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...
s
, denoted by
, is a
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, a binary operation ...
which takes a large graph (
) and a small graph (
) and produces a graph that approximately inherits the size of the large one but the
degree of the small one. An important property of the zig-zag product is that if
is a good
expander, then the expansion of the resulting graph is only slightly worse than the expansion of
.
Roughly speaking, the zig-zag product
replaces each vertex of
with a copy (cloud) of
, and connects the vertices by moving a small step (zig) inside a cloud, followed by a big step (zag) between two clouds, and finally performs another small step inside the destination cloud. More specifically, the start and endpoints for each edge are at the beginning and end of this "zig-zag-zig" process starting at the points in the
replacement product of the two graphs.
The zigzag product was introduced by . When the zig-zag product was first introduced, it was used for the explicit construction of constant degree expanders and extractors. Later on, the zig-zag product was used in
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
to prove that
symmetric logspace and
logspace are equal .
Definition
Let
be a
-regular graph on