Экспандер (теория графов)

В комбинаторике экспандером (или расширяющим графом) (expander graph) называется сильно связанный разреженный граф, при этом связность определяется по вершинам, дугам или спектру (смотрите ниже).

Экспандеры – это очень интересный класс графов, изучение которых первыми начали московские математики М. С. Пинскер, Л. А. Бассалыго и Г.А.Маргулис в семидесятые годы прошлого века. За прошедшее время эти графы нашли много неожиданных применений, например в теории сложности вычислений и в теории кодирования. Загадочным образом они оказались также связаны с далекими от классической теории графов разделами современной математики, например, с теорией групп и теорией чисел, и являются в настоящее время предметом активных исследований, ведущихся, в основном зарубежными математиками. Библиография по этой теме насчитывает сотни публикаций.

Определение

Экспандер – это конечный ненаправленный мультиграф, в котором любое подмножество вершин, не являясь "слишком большим", имеет "сильную" связность. Различные формализации этих понятий дают различные типы экспандеров: рёберный расширитель, вершинный расширитель, и спектральный расширитель.

Несвязный граф не является экспандером. Любой связный граф является экспандером, однако различные связные графы имеют различные параметры расширителя. Полный граф имеет лучшие параметры расширителя , но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.

Рёберное расширение

Рёберное расширение (также изопериметрическое число или константа Чиигера) h(G) графа G для n вершин определяется как

$h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},$

где минимум берётся по всем непустым множествам S не более чем n/2 вершин и ∂(S) – граничные дуги множества S, т.е., множество дуг с единственной вершиной в S.

Вершинное расширение

Вершинное изопериметрическое число $h_{\text{out}}(G)$ (также вершинное раширение) графа G определяется как

$h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},$

где $\partial _{\text{out}}(S)$ – внешняя граница S, т.е. множество вершин из $V(G)\setminus S$, имеющих как минимум одного соседа в S. В варианте этого определения (называемом уникальным соседним расширением) $\partial _{\text{out}}(S)$ заменяется на множество вершин из V с точностью одним соседом из S.

Вершинное изопериметрическое число $h_{\text{in}}(G)$ графа G определяется как

$h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},$

где $\partial _{\text{in}}(S)$ – внутренняя граница S, т.е. множество вершин S, имеющих как минимум одного соседа в $V(G)\setminus S$.

Спектральное расширение

Если G является d-регулярным, возможно определение в терминах линейной алгебры на основе собственных значений матрицы смежности A = A(G) графа G, где $A_{ij}$ – число дуг между вершинами i и j.. Поскольку A является симметричной, согласно спектральной теореме, A имеет n действительных собственных значений $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$. Известно, что эти значения лежат в промежутке [−d, d].

Граф регулярен тогда и только тогда, когда вектор $u\in \mathbb {R} ^{n}$ с $u_{i}=1$ для всех i = 1, ..., n является собственным вектором матрицы A, а его собственное число будет постоянной степенью графа. Таким образом, мы имеем Au = du, и u – собственный вектор матрицы A с собственными значениями λ₁ = d, где d – степень вершин графа G. Спектральный зазор графа G определяется как d−λ₂ и является мерилом спектрального расширения графа G.

Известно, что λ_n = −d тогда и только тогда, когда G – двудольный. Во многих случаях необходимо, например в Шаблон:Не переведно 5, необходимо ограничить снизу не только зазор между λ₁ и λ₂, но и зазор между λ₁ и вторым максимальным по модулю собственным значением:

$\lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}$.

Поскольку это собственное значение соответствует некоторому собственному вектору, ортогональному u, его можно определить, используя равенство Рэлея:

$\lambda =\max _{0\neq v\perp u}{\frac {\|Av\|_{2}}{\|v\|_{2}}},$

где

$\|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}$

– евклидова норма вектора $v\in \mathbb {R} ^{n}$.

Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица ${\tfrac {1}{d}}A$, являющаяся матрицей переходов графа G. Все её собственные значения лежат между −1 и 1. Если граф не регулярен, спектр графа может быть определён аналогичным образом , используя собственные значения матрицы Кирхгофа. Для направленного графа используются сингулярные значения матрицы сопряжения A, которые равны квадратным корням из собственных значений симметричной матрицы A^TA.

Взаимосвязь различных видов расширения

Вышеупомянутые виды расширения взаимосвязаны. В частности, для любого d-регулярного графа G,

$h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G).$

Следовательно, для графов постоянной степени, вершинное и рёберное расширение равны по величине.

Неравенства Чигера

В случае, когда G является d-регулярным графом, имеется соотношение между h(G) и спектральным зазором d − λ₂ графа G. Неравенство, полученное Таннером (Tanner) и, независимо, Ногом (Noga Alon) и Милманом (Vitali Milman) , утверждает, что

${\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.$

Это неравенство тесно связано с границей Чиигера для цепей Маркова и может рассматриваться как дискретная версия неравенства Чиигера в геометрии Римана.

Изучается также похожая связь между вершинными изопериметрическими числами и спектральным зазором . Заметим, что λ₂ в статье соответствует 2(d − λ₂) здесь

$h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1$

$h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.$

Асимптотически числа ${\frac {h^{2}}{d}}$, $h_{\text{out}}$ и $h_{\text{in}}^{2}$ ограничены сверху спектральным зазором $O(d-\lambda _{2})$.

Конструирование

Существуют три основные стратегии создания семейств графов расширений. Первая стратегия – алгебраическая и теоретико-групповая, вторая – аналитическая, использующая аддитивную комбинаторику, и третья – комбинаторная, использующая зигзаг-произведение и связанные комбинаторные произведения.

Маргулис-Габбер-Галил

Алгебраическое конструирование, основанное на графах Кэли, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером (Gabber) и Галилом (Galil). Для любого натурального n строим граф, G_n со множеством вершин $\mathbb {Z} _{n}\times \mathbb {Z} _{n}$, где $\mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z}$. Для любой вершины $(x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}$, её восемь соседей будут

$(x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).$

Выполняется следующая теорема:

Теорема. Для всех n граф G_n второе по величине собственное число $\lambda (G)\leq 5{\sqrt {2}}$.

Граф Рамануджана

По теореме Алона (Alon) и Боппана (Boppana) для всех достаточно больших d-регулярных графов выполняется неравенство $\lambda \geq 2{\sqrt {d-1}}-o(1)$, где λ – второе по абсолютной величине собственное число. Для графов Рамануджана$\lambda \leq 2{\sqrt {d-1}}$. Таким образом, графы Рамануджана имеют асимптотически наименьшее возможное значение λ и являются превосходными спектральными расширителями.

Александр Любоцкий, Филипс и Сарнак (1988), Маргулис (1988) и Моргенштерн (1994) показали как можно явно сконструировать граф Рамануджана. По теореме Фридмана (Friedman,2003) случайный d-регулярный граф с n вершинами является почти графом Рамануджана, поскольку выполняется

$\lambda \leq 2{\sqrt {d-1}}+\epsilon$

с вероятностью $1-o(1)$ при $n\rightarrow \infty$.

Приложения и полезные свойства

Первоначально интерес к экспандерам возник с целью построения устойчивой сети (телефонов или компьютеров) – число дуг графов расширения с ограниченным значением регулярности растет линейно по отношению к числу вершин.

Экспандеры нашли широкое применение в теории вычислительных машин и систем, для построения алгоритмов, корректирующих кодах, экстракторах, генераторах псевдослучайных чисел, сетях сортировки и компьютерных сетях. Они также используются для доказательства многих важных результатов в теории вычислительной сложности, таких как SL=L и Теорема PCP . В rриптографии экспандеры используются для создания хеш-функций.

Ниже приведены некоторые свойства экспандеров, считающиеся полезными во многих областях.

Лемма о перемешивании

Основная статья: Лемма о перемешивании

Лемма о перемешивании утверждает, что для любых двух подмножеств вершин $S,T\subseteq V$ число рёбер между S и T is примерно равна числу рёбер в случайном d-регулярном графе. Приближении тем лучше, чем меньше $\lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}$. В случайном d-регулярном графе, также как и в случайном графе Эрдёша — Реньис вероятностью d/n выбора ребра, ожидается ${\tfrac {d}{n}}\cdot |S|\cdot |T|$ рёбер между S и T.

Более формально, пусть E(S, T) обозначает число рёбер между S и T. Если эти два множества пересекаются, дуги в пересечении считаются дважды, так что

$E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S)$.

Лемма о перемешивании утверждает, что

$\left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq d\lambda {\sqrt {|S|\cdot |T|}},$

где λ – абсолютное значение нормализованного второго по величине собственного значения.

Блуждания по экспандеру

Основная статья: Блуждания по экспандеру

Согласно границе Чернова, если выбирать много независимых случайных значений из интервала [−1, 1], с большой степенью вероятности среднее выбранных значений будет близко к математическому ожиданию случайной переменной. Лемма о блуждании по экспандеру, согласно статьям Аджтари, Комлоша и Семереди и Гилмана, утверждает, что то же самое верно и для блужданий по экспандеру. Это полезно в теории дерандомизации, поскольку блуждание по экспандеру использует много меньше случайных бит чем случайная независимая выборка.

Смотрите также

• Алгебраическая связность
• Зигзаг произведение

Внешние ссылки

• Brief introduction in Notices of the American Mathematical Society
• Introductory paper by Michael Nielsen
• Lecture notes from a course on expanders (by Nati Linial and Avi Wigderson)
• Lecture notes from a course on expanders (by Prahladh Harsha)
• Definition and application of spectral gap