Изменения
→Маргулис-Габбер-Галил
Существуют три основные стратегии создания семейств графов расширений[6]. Первая стратегия — алгебраическая и теоретико-групповая, вторая — аналитическая, использующая аддитивную комбинаторику, и третья — комбинаторная, использующая зигзаг-произведение и связанные комбинаторные произведения.
===Маргулис-Габбер-Галил===
Алгебраическое конструирование, основанное на графах Кэли, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером (Gabber) и Галилом (Galil)[7]. Для любого натурального <tex>n </tex> строим граф, Gn <tex>G_{n}</tex> со множеством вершин <tex>\mathbb {Z} _{n}\times \mathbb {Z} _{n}</tex>, где <tex>\mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} </tex> . Для любой вершины <tex>(x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}</tex>, её восемь соседей будут <tex>(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).<// formulastex>
Выполняется следующая теорема:
{{Теорема|statement=Для всех <tex>n</tex> граф <tex>Gn</theoremtex> второе по величине собственное число <tex>\lambda(G)\leq 5 \sqrt{2}</tex>.}}
===Граф Рамануджана===
По теореме Алона (Alon) и Боппана (Boppana) для всех достаточно больших d-регулярных графов выполняется неравенство \lambda \geq 2{\sqrt {d-1}}-o(1), где λ — второе по абсолютной величине собственное число[1]. Для графов Рамануджана[en]\lambda \leq 2{\sqrt {d-1}} [1]. Таким образом, графы Рамануджана имеют асимптотически наименьшее возможное значение λ и являются превосходными спектральными расширителями.
