Editing Expander graph (section)

=== Zig-zag product ===
{{Main|Zig-zag product}}
[[Omer Reingold|Reingold]], [[Salil Vadhan|Vadhan]], and [[Avi Wigderson|Wigderson]] introduced the zig-zag product in 2003.<ref name=":0">{{Cite book|last1=Reingold|first1=O.|last2=Vadhan|first2=S.|last3=Wigderson|first3=A.|title=Proceedings 41st Annual Symposium on Foundations of Computer Science |chapter=Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors |chapter-url=http://dx.doi.org/10.1109/sfcs.2000.892006|year=2000|pages=3–13|publisher=IEEE Comput. Soc|doi=10.1109/sfcs.2000.892006|isbn=0-7695-0850-2|s2cid=420651}}</ref>  Roughly speaking, the zig-zag product of two expander graphs produces a graph with only slightly worse expansion. Therefore, a zig-zag product can also be used to construct families of expander graphs. If {{mvar|G}} is a {{math|(''n'', ''d'', ''λ''{{sub|1}})}}-graph and {{mvar|H}} is an {{math|(''m'', ''d'', ''λ''{{sub|2}})}}-graph, then the zig-zag product {{math|''G'' ◦ ''H''}} is a {{math|(''nm'', ''d''{{sup|2}}, ''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}))}}-graph where {{mvar|φ}} has the following properties.

# If {{math|''λ''{{sub|1}} < 1}} and {{math|''λ''{{sub|2}} < 1}}, then {{math|''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}) < 1}};
# {{math|''φ''(''λ''{{sub|1}}, ''λ''{{sub|2}}) ≤  ''λ''{{sub|1}} + ''λ''{{sub|2}}}}.
Specifically,<ref name=":0" />
:<math>\phi(\lambda_1, \lambda_2)=\frac{1}{2}(1-\lambda^2_2)\lambda_2 +\frac{1}{2}\sqrt{(1-\lambda^2_2)^2\lambda_1^2 +4\lambda^2_2}.</math>

Note that property (1) implies that the zig-zag product of two expander graphs is also an expander graph, thus zig-zag products can be used inductively to create a family of expander graphs.

Intuitively, the construction of the zig-zag product can be thought of in the following way. Each vertex of {{mvar|G}} is blown up to a "cloud" of {{mvar|m}} vertices, each associated to a different edge connected to the vertex. Each vertex is now labeled as {{math|(''v'', ''k'')}} where {{mvar|v}} refers to an original vertex of {{mvar|G}} and {{mvar|k}} refers to the {{mvar|k}}th edge of {{mvar|v}}. Two vertices, {{math|(''v'', ''k'')}} and {{math|(''w'',''ℓ'')}} are connected if it is possible to get from {{math|(''v'', ''k'')}} to {{math|(''w'', ''ℓ'')}} through the following sequence of moves.

# ''Zig'' – Move from {{math|(''v'', ''k'')}} to {{math|(''v'', ''k' '')}}, using an edge of {{mvar|H}}.
# Jump across clouds using edge {{mvar|k'}} in {{mvar|G}} to get to {{math|(''w'', ''ℓ&prime;'')}}.
# ''Zag'' – Move from {{math|(''w'', ''ℓ&prime;'')}} to {{math|(''w'', ''ℓ'')}} using an edge of {{mvar|H}}.<ref name=":0" />