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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

с вероятностью ${\displaystyle 1-o(1)}$ при ${\displaystyle n\rightarrow \infty }$ [16].

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

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

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

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

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

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

Недавно Билу (Bilu) и Линайл (Linial) показали, что обратное тоже верно, то есть, при условии выполнения неравенства из леммы второе по величине собственное значение равно ${\displaystyle O(d\lambda \cdot (1+\log(1/\lambda )))}$[21].

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