Constant-degree expanders construction based on zig-zag product

You need to know: Direct product , graph, vertex set, edges, neighbours, edge expansion of a graph, family of expanders.

Background: For any graph G, a 2-edge path is a set of vertices , connected by edges and . Now, the graph is the graph with the same vertices as G such that for every 2-edge path in G, we put an edge between i and j in .

Denote [N] the set of integers . We say that graph G is D-regular if each vertex has D neighbours; it is also D-coloured if its edges are marked with labels from [D] such that no 2 edges with the same mark share a vertex. For a label and a vertex v let v[i] be the neighbour of v along the edge marked i.

Let be a -regular -coloured graph on , and be a -regular -coloured graph on . Then zig-zag product of and is a -regular graph on defined as follows: For all , , , the edge connects the vertex to the vertex .

The Theorem: On 10th July 2000, Omer Reingold, Salil Vadhan, and Avi Wigderson submitted to Annals of Mathematics a paper in which they proved that the sequence given by , (where H is d-regular graph of size and sufficiently high edge expansion) is a -regular family of expanders.

Short context: Explicit and efficient constructions of families of expanders with various “good” properties have applications in many areas of mathematics and computer sciences. There are many such constructions starting from 1973 work of Margulis, but, before 2000, all the constructions were either algebraic or complicated. The Theorem provides a simple combinatorial construction of a family of constant-degree expanders.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 2.3 of this book for an accessible description of the Theorem.

Go to the list of all theorems