Editing Expander graph (section)

===Margulis–Gabber–Galil===
[[Abstract algebra|Algebraic]] constructions based on [[Cayley graph]]s are known for various variants of expander graphs. The following construction is due to Margulis and has been analysed by Gabber and Galil.<ref>see, e.g., p.9 of {{harvtxt|Goldreich|2011}}</ref> For every natural number {{mvar|n}}, one considers the graph {{mvar|G{{sub|n}}}} with the vertex set <math>\mathbb Z_n \times \mathbb Z_n</math>, where <math>\mathbb Z_n=\mathbb Z/n\mathbb Z</math>: For every vertex <math>(x,y)\in\mathbb Z_n \times \mathbb Z_n</math>, its eight adjacent vertices are

:<math>(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).</math>

Then the following holds:

<blockquote>'''Theorem.''' For all {{mvar|n}}, the graph {{mvar|G{{sub|n}}}} has second-largest eigenvalue <math>\lambda(G)\leq 5 \sqrt{2}</math>.</blockquote>