Графы-экспандеры — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Применение экспандеров)
м (rollbackEdits.php mass rollback)
 
(не показана 101 промежуточная версия 5 участников)
Строка 1: Строка 1:
'''Граф-экспандер''' (или расширяющийся граф, англ. ''expander graph'') - в комбинаторике сильно разреженный граф, при этом связность определяется по вершинам, дугам или спектру.
+
{{Определение
 +
|definition=
 +
'''Граф-экспандер''' (или расширяющийся граф, англ. ''expander graph'') {{---}} в комбинаторике сильно разреженный [[Основные определения теории графов#Ориентированные графы|граф]], при этом связность определяется по вершинам, дугам или спектру. Это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность.
 +
}}
 +
 
 +
Любой связный граф является экспандером, однако различные связные [[Основные определения теории графов#Ориентированные графы|графы]] имеют различные параметры расширителя. [[Основные определения теории графов#Часто используемые графы|Полный граф]] имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.
 +
== Основные определения ==
 +
 
 +
{{Определение
 +
|definition=
 +
'''Множество соседей''' (англ. ''set of neighbors'') для множества вершин <tex>S</tex> называется <tex>\Gamma(S) = \{v: \exists w \in S:\ (v, w) \in E\}</tex>.
 +
}}
 +
'''Замечание:''' в графе могут присутствовать кратные ребра и петли. Если у каждой вершины есть петли, то <tex>\forall S: S \supseteq \Gamma(S)</tex>.
 +
 
 +
===Вершинное расширение===
 +
''Вершинное изопериметрическое число'' <tex>h_{out}(G)</tex> (также ''вершинное раширение'') графа <tex>G</tex> определяется как
 +
 
 +
<tex>h_{out}(G) = \min\limits_{0 < |S|\leqslant \cfrac{n}{2}} \cfrac{|\Gamma_{\text{out}}(S)|}{|S|}</tex>,
 +
 
 +
где <tex>\Gamma_{\text{out}}(S)</tex> — ''внешняя граница'' <tex>S</tex>, то есть множество вершин из <tex>V(G)\setminus S</tex>, имеющих как минимум одного соседа в <tex>S</tex>.
 +
 
 +
<tex>\Gamma_{\text{out}}(S) = \{v \in V(G) \diagdown S: \exists w \in S (v, w) \in E\}</tex>.
 +
 
 +
''Вершинное изопериметрическое число'' <tex>h_{in}(G)</tex> графа <tex>G</tex> определяется как
 +
 
 +
<tex>h_{in}(G) = \min\limits_{0 < |S|\leqslant \cfrac{n}{2}} \cfrac{|\Gamma_{\text{in}}(S)|}{|S|}</tex>,
 +
 
 +
 
 +
где <tex>\Gamma_{in}(S)</tex> — ''внутренняя граница'' <tex>S</tex>, то есть множество вершин <tex>S</tex>, имеющих как минимум одного соседа в <tex>V(G)\setminus S</tex>.
 +
 
 +
<tex>\Gamma_{in}(S) = \Gamma(S) \diagdown \Gamma_{in}(S)</tex>
 +
==== Однородный (комбинаторный) экспандер ====
 +
{{Определение
 +
|definition=
 +
'''Однородный (комбинаторный) экспандер''' (англ. ''combinatorial expander'') называется [[Основные определения теории графов#Ориентированные графы|граф]] <tex>G = (V, E)</tex> с параметрами <tex>(n, d, \epsilon) \ (n = |V|</tex>, d {{---}} степень каждой вершины, константа <tex>\epsilon < 1)</tex>, если выполняется условие:
 +
для <tex>\ \forall S: S \subseteq V, \ |S| \leqslant \cfrac{n}{2} \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.
 +
}}
 +
'''Замечание:''' чем больше <tex>\epsilon</tex>, тем сильнее свойство расширения.
 +
{{Теорема
 +
|statement=
 +
Пусть <tex>\epsilon</tex> {{---}} некоторое положительное число меньшее <tex>1</tex>. Тогда для всех достаточно больших четных <tex>d = d(\epsilon)</tex> и всех <tex>n</tex> существует однородный (комбинаторный) экспандер с параметрами <tex>(n, d, \epsilon)</tex>.
 +
|proof=
 +
Мы выберем граф случайно и покажем, что с положительной (и даже довольно близкой к <tex>1</tex>) вероятностью такой граф оказывается экспандером. Отсюда будет следовать, что экспандеры существуют.
 +
 
 +
Оценим вероятность того, что полученный в результате граф не является экспандером, если найдется множество вершин <tex>S</tex> (состоящее из не более, чем <tex>\cfrac{n}{2}</tex> вершин), все соседи которого лежат в некотором множестве <tex>T</tex>, состоящем из <tex>\lfloor (1 + \epsilon)|S|\rfloor</tex> вершин.
 +
 
 +
Зафиксируем некоторые множества вершин <tex>S</tex> и <tex>T</tex>. Зафиксируем номер перестановки <tex>\pi_{i}</tex>. Вероятность того, что для каждой вершины <tex>v \in S</tex> второй конец ребра <tex>\{v, pi_{i}(v)\}</tex> попадёт в <tex>T</tex>, равна
 +
 
 +
<tex>\cfrac{|T|}{n} \cdot \cfrac{|T| - 1}{n - 1} \cdot \ldots \cdot \cfrac{|T| - |S| + 1}{n - |S| + 1} \leqslant \bigg(\cfrac{|T|}{n}\bigg)^{|S|}</tex>.
 +
 
 +
Поскольку мы выбираем <tex>\cfrac{d}{2}</tex> перестановок независимо, вероятность того, что данное событие произойдёт для всех <tex>i</tex> не превосходит <tex>\bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}}</tex>.
 +
Таким образом,
 +
 
 +
Вероятность, что свойство экспандерности графа нарушено небольше <tex>\sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}}</tex>,
 +
где суммирование происходит по всем множествам вершин <tex>S</tex> размера не более <tex>\cfrac{n}{2}</tex> и по всем множествам <tex>T</tex> размера <tex>\lfloor(1 + \epsilon)|S|\rfloor</tex>.
 +
 
 +
Оценим сумму:
 +
 
 +
<tex>\sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}} \leqslant \sum\limits_{s = 1}^{\tfrac{n}{2}} \dbinom{s}{n} \cdot \dbinom{(1 + \epsilon)s}{n} \cdot \bigg(\cfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd}{2}}</tex>. <tex>(1)</tex>
 +
 
 +
Каждый биномиальный коэффициент <tex>\dbinom{k}{n}</tex> можно оценить сверху величиной <tex>\bigg(\cfrac{ne}{k}\bigg)^{k}</tex>. Тогда
 +
 
 +
<tex>
 +
\sum\limits_{s = 1}^{\tfrac{n}{2}}
 +
  \bigg(\cfrac{ne}{s}\bigg)^{s} \cdot
 +
  \bigg(\cfrac{ne}{(1 + \epsilon)s}\bigg)^{(1 + \epsilon)s} \cdot
 +
  \bigg(\cfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd}{2}} =</tex>
 +
 
 +
<tex>\sum\limits_{s = 1}^{\tfrac{n}{2}} \bigg[\bigg(\cfrac{s}{n}\bigg)^{\tfrac{d}{2} - 2 - \epsilon} \cdot (1 + \epsilon)^{\tfrac{d}{2}} \cdot \cfrac{e^{1 + \epsilon} }{(1 + \epsilon)^{1 + \epsilon} }\bigg]^s</tex>. <tex>(2)</tex>
 +
 
 +
Заметим, что <tex>s \leqslant \cfrac{n}{2}</tex>, а <tex>1 + \epsilon < 2</tex>. Таким образом, можно подобрать такое
 +
<tex>d = d(\epsilon)</tex>, чтобы выражение в квадратных скобках в правой части <tex>(2)</tex> было меньше <tex>\cfrac{1}{2}</tex> при всех значениях <tex>\epsilon</tex>. Следовательно, сумма <tex>(1)</tex> меньше единицы. Что означает, что с положительной вероятностью случайный граф является экспандером с параметрами <tex>(n, d, \epsilon)</tex>.
 +
}}
 +
 
 +
==== Двудольный экспандер ====
 +
{{Определение
 +
|definition=
 +
'''Двудольный экспандер''' (англ. ''Bipartite expander'') называется [[Двудольные графы|двудольный граф]] <tex>G = (L,\ R,\ E)\ (L</tex> и <tex>R</tex> {{---}} вершины левой и правой доли соответственно, <tex>E</tex> {{---}} ребра графа <tex>G</tex>) с параметрами <tex>(n,\ m,\ d,\ e)\ (n = |L|,\ m = |R|,\ d</tex> - степень всех вершин в левой доле), если выполняется условие: для <tex>\forall S: S \subseteq L \ |S| \leqslant k \ \ |\Gamma(S)| > (1 - \epsilon)d|S|</tex>.
 +
}}
 +
'''Замечание 1:''' чем меньше значение <tex>\epsilon</tex> в данном определении, тем сильнее свойство расширения.
 +
 
 +
'''Замечание 2:''' в приложениях как правило используют двудольные экспандеры с <tex>\epsilon < \cfrac{1}{2}</tex>, а для применения в теории кодирования (для построения экспандерных кодов) часто требуются двудольные экспандеры с ещё меньшими значениями <tex>\epsilon</tex>.
 +
 
 +
{{Теорема
 +
|statement=
 +
Пусть <tex>\epsilon</tex> {{---}} некоторое положительное число. Тогда для <tex>\forall \ n</tex> и <tex>k \leqslant n</tex> найдется <tex>d = O(\log n)</tex> и <tex>m = O(dk)</tex> такие, что <tex>\exists</tex> двудольный экспандер с параметрами <tex>(n, m, d, k, \epsilon)</tex>.
 +
|proof=
 +
Выберем случайный граф, то есть для <tex>\forall \ v \in L</tex> случайно и независимо выбираем <tex>d</tex> соседей в <tex>R</tex> (разрешаются кратные ребра). Покажем с большой вероятностью такой граф оказывается экспандером.
 +
 
 +
Граф не является экспандером, если <tex>\exists T \subset R: \ |T| = (1 - \epsilon)d|S|</tex> и <tex>\exists S \subset L: \ \Gamma(S) = T</tex>.
 +
 
 +
Поскольку при случайном выборе графа мы приводим все <tex>nd</tex> рёбер случайно и независимо, то для <tex>\forall</tex> ребра вероятность того, что его правый конец окажется в фиксированном множестве <tex>T</tex>, равна <tex>\cfrac{|T|}{m}</tex>. Следовательно, вероятность, что свойство экспандерности графа нарушено <tex> \leqslant \ \sum\limits_{S, T}\bigg(\cfrac{|T|}{m}\bigg)^{sd}</tex>,
  
==Определение==
+
где суммирование происходит по всем множествам <tex>S \subset L \ |S| \leqslant k \ \forall T: T \subset R \ |T| = (1 - \epsilon)d|S| </tex>. Оценим данную сумму сверху:
''Граф-экспандер'' — это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность. Различные формализации этих понятий дают различные типы экспандеров: ''рёберный расширитель'', ''вершинный расширитель'', и ''спектральный расширитель''.
 
  
Несвязный граф не является экспандером. Любой связный граф является экспандером, однако различные связные графы имеют различные параметры расширителя. Полный граф имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.
+
<tex>\sum\limits_{s = 1}^{k} \dbinom{s}{n} \* \dbinom{(1 - \epsilon)sd}{m} \* \bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}</tex>.
  
===Реберное расширение===
+
Оценивая биномиальные коэффициенты, получаем, что сумма не превосходит
''Рёберное расширение'' (также ''изопериметрическое число'' или константа Чигера) <tex>h(G)</tex> графа <tex>G</tex> для <tex>n</tex> вершин определяется как
+
 
 +
<tex>
 +
\sum\limits_{s = 1}^{k}
 +
\bigg(\cfrac{ne}{s}\bigg)^{s} \cdot
 +
\bigg(\cfrac{me}{(1 - \epsilon)sd}\bigg)^{(1 - \epsilon)sd} \cdot
 +
\bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}
 +
\leqslant </tex>
 +
 
 +
<tex>\sum\limits_{s = 1}^{k}
 +
\bigg[\cfrac{ne}{s} \cdot
 +
\bigg(\cfrac{e^{\tfrac{1 - \epsilon}{\epsilon}} \cdot
 +
(1 - \epsilon)sd}{m}\bigg)^{\epsilon d}\bigg]^{s}
 +
</tex>.
  
<tex>h(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|}</tex>,
+
Положим <tex>m = Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных s выполнялось неравенство <tex>\cfrac{e^{\tfrac{1 - \epsilon}{\epsilon}} \cdot (1 - \epsilon)sd}{m} \leqslant \cfrac{1}{2}</tex>. Тогда выражение в квадратных скобках не превосходит <tex>\cfrac{ne}{2 ^ {\epsilon d}}</tex>. Остаётся выбрать <tex>d > \cfrac{1}{\epsilon}\log(2en)</tex>, и мы получаем <tex>\cfrac{ne}{2^{\epsilon d}} < \cfrac{1}{2}</tex>.
  
где минимум берётся по всем непустым множествам <tex>S</tex> не более чем <tex>n/2</tex> вершин и <tex>\partial(S)</tex> ''граничные дуги'' множества <tex>S</tex>, то есть, множество дуг с единственной вершиной в <tex>S</tex>.
+
Таким образом, для выбранных значений параметров сумм не превосходят <tex>1</tex>. Это означает, что с положительной вероятностью случайный двудольный граф является экспандером c параметрами <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex>.
 +
}}
 +
'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>.
  
===Вершинное расширение===
+
==== Теорема о паросочетаниях ====
''Вершинное изопериметрическое число'' <tex>h_{out}(G)</tex> (также ''вершинное раширение'') графа <tex>G</tex> определяется как
+
{{Теорема
 +
|statement=
 +
Пусть <tex>G</tex> {{---}} [[Двудольные графы|двудольный граф]].
 +
<tex>G</tex> имеет совершенное паросочетание тогда и только тогда, когда <tex>\forall S: S \supseteq L \ |S| \leqslant \Gamma(S)</tex>.
 +
|proof=
 +
Будем доказывать по индукции
  
<tex>h_{out}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|},</tex>
+
Для <tex>|L| = 1</tex> очевидно
  
где <tex>\partial_{\text{out}}(S)</tex> — ''внешняя граница'' <tex>S</tex>, то есть множество вершин из <tex>V(G)\setminus S</tex>, имеющих как минимум одного соседа в S. В варианте этого определения (называемом ''уникальным соседним расширением'') <tex>\partial_{\text{out}}(S)</tex> заменяется на множество вершин из <tex>V</tex> с ''точностью одним'' соседом из <tex>S</tex>.
+
Предположим, что верно для <tex>L: |L| < m</tex>
  
''Вершинное изопериметрическое число'' <tex>h_{in}(G)</tex> графа <tex>G</tex> определяется как
+
Рассмотрим два случая:
 +
# <tex>\forall S: S \supseteq L, |S| \neq 0</tex> строго расширяется, то есть <tex>|\Gamma(S)| > |S|</tex>. Выберем <tex>\forall x: x \supset V(L) : (x, y) \in E</tex>. Тогда рассмотрим двудольный граф <tex>G^{*}</tex>, у которого левая доля <tex>L^{*} = L \diagdown {x}</tex>, а правая <tex>R^{*} = R \diagdown {y}</tex>. Так как <tex>\forall S: S \supset L</tex> удовлетворяет строгому неравенству теоремы, то каждое подмножество <tex>L^{*}</tex> удовлетворяет неравенству, поскольку только одна вершина <tex>y</tex> была удалена из <tex>R</tex>. Следовательно, по предположению индукции меньший граф <tex>G^{*}</tex> имеет паросочетание. К этому паросочетанию добавляем ребро (x, y) что дает совершенное паросочетание.
 +
# Пусть <tex>\exists\ T \in L, \ |T| \neq 0</tex> такое, что <tex>|\Gamma(T)| = |T|</tex>. Рассмотрим порожденные графы <tex>G_{1} = T \cup \Gamma(T)</tex> и <tex>G_{2} = L \diagdown T \cup R \diagdown \Gamma(T)</tex>. По предположению индукции <tex>G_{1}</tex> имеет совершенное паросочетание (Заметим, что предположение индукции не может использовано непосредственно на <tex>G_{2}</tex>). Пусть <tex>S \supseteq L \diagdown T</tex>, тогда: <tex>\Gamma_{G_{2}}(S) = \Gamma_{G}(S \cup T) \diagdown \Gamma_{G}(T) \ \Rightarrow</tex> <tex>|\Gamma_{G_{2}}| \geqslant |S \cup T| - |T| = |S|</tex> Неравенство верно, поскольку <tex>S \cup T</tex> удовлетворяет <tex>|\Gamma_{G}(S \cup T)| \geqslant |S \cup T|</tex> и по предположению <tex>|\Gamma_{G}(T)| = |T|</tex>. Следовательно, <tex>G_{2}</tex> также удовлетворяет неравенству теоремы и по предположению индукции имеет паросочетание. Объединение совершенных паросочетаний <tex>G_{1}</tex> и <tex>G_{2}</tex> {{---}} паросочетание для <tex>G</tex>.
 +
}}
 +
 
 +
===Реберное расширение===
 +
''Рёберное расширение'' (также ''изопериметрическое число'' или константа Чигера<ref>[[wikipedia:Cheeger_constant|Wikipedia {{---}} константа Чигера]]</ref>) <tex>h(G)</tex> графа <tex>G</tex> для <tex>n</tex> вершин определяется как
  
<tex>h_{in}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{in}}(S)|}{|S|},</tex>
+
<tex>h(G) = \min\limits_{0 < |S|\leqslant \cfrac{n}{2}} \cfrac{|\partial_{\text{out}}(S)|}{|S|}</tex>,
  
где <tex>∂_{in}(S)</tex> — ''внутренняя граница'' <tex>S</tex>, то есть множество вершин <tex>S</tex>, имеющих как минимум одного соседа в <tex>V(G)\setminus S</tex>.
+
где минимум берётся по всем непустым множествам <tex>S</tex> не более чем <tex>\cfrac{n}{2}</tex> вершин и <tex>\partial(S)</tex> — ''граничные дуги'' множества <tex>S</tex>, то есть, множество дуг с единственной вершиной в <tex>S</tex>.
  
 
===Спектральное расширение===
 
===Спектральное расширение===
  
Если <tex>G</tex> является d-регулярным, возможно определение в терминах линейной алгебры на основе собственных значений матрицы смежности <tex>A = A(G)</tex> графа <tex>G</tex>, где <tex>A_{ij}</tex> число дуг между вершинами <tex>i</tex> и <tex>j</tex>. Поскольку <tex>A</tex> является симметричной, согласно спектральной теореме, <tex>A</tex> имеет <tex>n</tex> действительных собственных значений <tex>\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_{n}</tex>. Известно, что эти значения лежат в промежутке <tex>[−d, d]</tex>.
+
Если <tex>G</tex> является [[Основные определения теории графов#Часто используемые графы|d-регулярным]], возможно определение в терминах [[Алгебра|линейной алгебры]] на основе собственных значений [[Матрица смежности графа|матрицы смежности]] <tex>A = A(G)</tex> графа <tex>G</tex>, где <tex>A_{ij}</tex> {{---}} число дуг между вершинами <tex>i</tex> и <tex>j</tex>. Поскольку <tex>A</tex> является симметричной, согласно спектральной теореме<ref>[[wikipedia:Spectral theorem|Wikipedia {{---}} спектральная теорема]]</ref>, <tex>A</tex> имеет <tex>n</tex> действительных собственных значений <tex>\lambda_{1} \ge \lambda_{2} \ge \cdots \ge \lambda_{n}</tex>. Известно, что эти значения лежат в промежутке <tex>[-d, d]</tex>.
Граф регулярен тогда и только тогда, когда вектор <tex>u\in \mathbb {R} ^{n} с u_{i}=1</tex> для всех <tex>i = 1, …, n</tex> является собственным вектором матрицы <tex>A</tex>, а его собственное число будет постоянной степенью графа. Таким образом, мы имеем <tex>Au = du</tex>, и <tex>u</tex> — собственный вектор матрицы <tex>A</tex> с собственными значениями <tex>λ1 = d</tex>, где <tex>d</tex> — степень вершин графа <tex>G</tex>. Спектральный зазор графа <tex>G</tex> определяется как <tex>d−λ2</tex> и является мерилом спектрального расширения графа <tex>G</tex>.
+
Граф регулярен тогда и только тогда, когда вектор <tex>u\in \mathbb {R} ^{n}</tex> с <tex>u_{i}=1</tex> для всех <tex>i = 1 \ldots n</tex> является собственным вектором матрицы <tex>A</tex>, а его собственное число будет постоянной степенью графа. Таким образом, мы имеем <tex>Au = du</tex>, и <tex>u</tex> — собственный вектор матрицы <tex>A</tex> с собственными значениями <tex>\lambda_{1} = d</tex>, где <tex>d</tex> — степень вершин графа <tex>G</tex>. Спектральный зазор графа <tex>G</tex> определяется как <tex>d-\lambda_{2}</tex> и является мерилом спектрального расширения графа <tex>G</tex>.
  
Известно, что <tex>\lambda_n = −d</tex> тогда и только тогда, когда <tex>G</tex> двудольный. Во многих случаях, например в лемме о перемешивании, необходимо ограничить снизу не только зазор между <tex>\lambda_1</tex> и <tex>\lambda_2</tex>, но и зазор между <tex>\lambda_1</tex> и вторым максимальным по модулю собственным значением:
+
Известно, что <tex>\lambda_{n} = -d</tex> тогда и только тогда, когда <tex>G</tex> {{---}} [[Двудольные графы|двудольный]]. Во многих случаях, например в [[Графы-экспандеры#Лемма о перемешивании|лемме о перемешивании]], необходимо ограничить снизу не только зазор между <tex>\lambda_{1}</tex> и <tex>\lambda_{2}</tex>, но и зазор между <tex>\lambda_{1}</tex> и вторым максимальным по модулю собственным значением:
  
<tex>\lambda=\max\{|\lambda_2|, |\lambda_{n}|\}</tex>
+
<tex>\lambda=\max\{|\lambda_{2}|, |\lambda_{n}|\}</tex>
  
 
Поскольку это собственное значение соответствует некоторому собственному вектору, ортогональному <tex>u</tex>, его можно определить, используя отношение Рэлея:
 
Поскольку это собственное значение соответствует некоторому собственному вектору, ортогональному <tex>u</tex>, его можно определить, используя отношение Рэлея:
<tex>\lambda=\max_{0\neq v\perp u} \frac{\|Av\|_2}{\|v\|_2},</tex>
+
<tex>\lambda=\max\limits_{0\neq v\perp u} \cfrac{\|Av\|_2}{\|v\|_2},</tex>
gde
 
<tex>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1/2}</tex>
 
— евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>.
 
  
Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\tfrac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>−1</tex> и <tex>1</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения матрицы Кирхгофа. Для направленного графа используются сингулярные значения матрицы сопряжения A, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</tex>.
+
где <tex>\|v\|_2=\left(\sum\limits_{i=1}^{n} v_i^2\right)^{\tfrac{1}{2}}</tex> {{---}} евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>.
 +
 
 +
Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\cfrac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>(-1, 1)</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения [[Матрица Кирхгофа|матрицы Кирхгофа]]. Для направленного графа используются сингулярные значения матрицы сопряжения <tex>A</tex>, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</tex>.
  
 
==Конструирование==
 
==Конструирование==
Существуют три основные стратегии создания семейств графов расширений[6]. Первая стратегия алгебраическая и теоретико-групповая, вторая аналитическая, использующая аддитивную комбинаторику, и третья комбинаторная, использующая зигзаг-произведение и связанные комбинаторные произведения.
+
Существуют три основные стратегии создания семейств графов расширений. Первая стратегия {{---}} алгебраическая и теоретико {{---}} групповая, вторая {{---}} аналитическая, использующая аддитивную комбинаторику, и третья {{---}} комбинаторная, использующая зигзаг-произведение и связанные комбинаторные произведения.
 
===Маргулис-Габбер-Галил===
 
===Маргулис-Габбер-Галил===
Алгебраическое конструирование, основанное на графах Кэли, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером (Gabber) и Галилом (Galil). Для любого натурального <tex>n</tex> строим граф, <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>, её восемь соседей будут
+
[[Алгебра|Алгебраическое]] конструирование, основанное на графах Кэли<ref>[[wikipedia:Cayley_graph|Wikipedia {{---}} граф Кэли]]</ref>, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером и Галилом <ref>Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291</ref>.
 +
 
 +
В качестве множества вершин графа возьмём <tex>V = \mathbb Z _{n}\times \mathbb {Z} _{n}</tex> (таким образом, граф будет содержать <tex>n^{2}</tex> вершин). Каждая вершина <tex>(x, y)</tex> из <tex>\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)).</tex>
 
<tex>(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).</tex>
 +
 +
(все арифметические вычисления производятся по модулю <tex>n</tex>). Таким образом, степень каждой вершины графа равна 8. При достаточно больших <tex>n</tex> в этом графе не будет кратных рёбер.
  
 
Выполняется следующая теорема:
 
Выполняется следующая теорема:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Для всех <tex>n</tex> граф <tex>Gn</tex> второе по величине собственное число
+
<tex>\forall n</tex> граф <tex>G_{n}</tex> второе по величине собственное число удовлетворяет неравенству
  
<tex>\lambda(G)\leq 5 \sqrt{2}</tex>.}}
+
<tex>\lambda(G)\leqslant 5 \sqrt{2}</tex>.
 +
}}
  
 
===Граф Рамануджана===
 
===Граф Рамануджана===
<tex>d</tex>-регулярный граф называется графом Рамануджана, если его второе по модулю собственное число не превосходит <tex>2{\sqrt {d-1}}</tex>. Любоцкий, Сарнак, Филлипс и Маргулис указали явную конструкцию графов Кэли, являющихся графами Рамануджана. Опишем эту конструкцию.
+
{{Теорема
Пусть <tex>p</tex> и <tex>q</tex> простые числа, <tex>p = 1</tex> <tex>mod</tex> <tex>4</tex> и <tex>q = 1</tex> <tex>mod</tex> <tex>4</tex>. В качестве группы <tex>G</tex> возьмём <tex>PGL(2, \mathbb Z/q{\mathbb Z})</tex>, т.е. невырожденные матрицы 2 × 2 над полем вычетов по модулю <tex>q</tex>, профакторизованные по отношению пропорциональности (с обычной операцией матричного умножения).
+
|statement=
Далее мы зададим в этой группе симметричное множество <tex>S</tex>. Выберем такое целое <tex>i</tex>, что <tex>i^2 = −1</tex> <tex>mod</tex> <tex>q</tex>. Можно доказать, что тогда имеется ровно <tex>(p + 1)</tex> целочисленное решение уравнения
+
[[Основные определения теории графов#Часто используемые графы|d-регулярный граф]] называется графом Рамануджана, если его второе по модулю собственное число <tex> \lambda \leqslant 2\sqrt {d-1} - o(1)</tex>.
 
+
}}
<tex>a_0^2 + a_1^2 + a_3^2 = p</tex>
 
 
 
такое, что <tex>a_0</tex> положительно и нечётно, а <tex>a_1</tex>, <tex>a_2</tex>, <tex>a_3</tex> чётны. Каждой такой четвёрке сопоставим матрицу
 
 
 
<tex>A = \begin{pmatrix} a_0 + ia_1 & a_2 + ia_3\\ -a_2 + ia_3 & a_0 - ia_1 \end{pmatrix}</tex>
 
  
Эти матрицы образуют множество S.
+
'''Замечание:''' случайный [[Основные определения теории графов#Часто используемые графы|d-регулярный граф]] с <tex>n</tex> вершинами почти является графом Рамануджана, так как выполняется неравенство <tex> \lambda \leqslant 2\sqrt {d-1} + \epsilon</tex> с вероятностью <tex>1 - o(1)</tex> при <tex>n \to \inf</tex>.
Нетрудно понять, что граф Кэли <tex>(G, S)</tex> состоит из <tex>\Theta(q^3)</tex> вершин, и степень каждой вершины равна <tex>(p + 1)</tex>. Свойства данного графа зависят от соотношения <tex>p</tex> и <tex>q</tex>. Рассмотрим случай, когда p является квадратичным вычетом по модулю <tex>q</tex>. Тогда полученный граф Кэли состоит из двух связных компонент (поскольку все матрицы из <tex>S</tex> лежат в подгруппе <tex>G</tex> индекса два — подгруппе матриц, определитель которых является квадратичным вычетом). Обозначим <tex>X^{p,q}</tex> связную компоненту полученного графа. Можно доказать, что у <tex>X^{p,q}</tex> второе по абсолютной величине собственное число не превосходит <tex>2{\sqrt{p}}</tex>, т.е. мы получили граф Рамануджана.
 
  
 
==Примеры применения экспандеров==
 
==Примеры применения экспандеров==
 
===Коды, исправляющие ошибки===
 
===Коды, исправляющие ошибки===
С помощью расширяющего графа можно посторить линейный код, позволяющий исправлять ошибки в доле <tex>\delta = 1/(2000d)</tex> битов. Чтобы задать линейный код с длиной кодового слова n, достаточно описать его проверочную матрицу <tex>H</tex> <tex>(</tex>слово <tex>x \in \{0, 1\}^n</tex> является кодовым словом если и только если <tex>Hx^t = 0)</tex>. Другими словами, нужно задать систему линейных уравнений для переменных <tex>x_1, . . . , x_n;</tex> решения этой системы и будут кодовыми словами.
+
С помощью расширяющего графа можно посторить линейный код, позволяющий исправлять ошибки в доле <tex>\delta = \cfrac{1}{2000d}</tex> битов. Чтобы задать линейный код с длиной кодового слова n, достаточно описать его проверочную матрицу <tex>H</tex> <tex>(</tex>слово <tex>x \in \{0, 1\}^n</tex> является кодовым словом если и только если <tex>Hx^t = 0)</tex>. Другими словами, нужно задать систему линейных уравнений для переменных <tex>x_1, \ldots , x_n</tex> решения этой системы и будут кодовыми словами.
 +
 
 
===Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел===
 
===Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел===
{{Определение
 
|definition=Язык <tex>L</tex> принадлежит сложностному классу <tex>RP</tex>, если существует полиномиальный алгоритм <tex>A</tex> такой что
 
1. для <tex>x \in L</tex> для всех <tex>r \in \{0, 1\}^{poly(n)}</tex> <tex>A(x, r) = 1</tex>
 
2. для <tex>x \notin L</tex> не более чем для 1/2000 всех <tex>r \in \{0, 1\}^{poly(n)}</tex> может выполняться <tex>A(x, r) = 1</tex>
 
}}
 
 
 
Покажем, что для любого <tex>\epsilon > 0</tex> полиномиальный вероятностный алгоритм A можно модифицировать таким образом, чтобы вероятность ошибки уменьшилась до <tex>\epsilon</tex>, а число используемых случайных битов не изменится.
 
Покажем, что для любого <tex>\epsilon > 0</tex> полиномиальный вероятностный алгоритм A можно модифицировать таким образом, чтобы вероятность ошибки уменьшилась до <tex>\epsilon</tex>, а число используемых случайных битов не изменится.
  
Пусть исходный алгоритм использует <tex>k = k(n)</tex> случайных битов для вычислений на входах длины <tex>n</tex>. Зафиксируем <tex>(2^k, 2^k, d)</tex> - экспандер <tex>G</tex>, где <tex>d > 1/\epsilon</tex>. Новый алгоритм действует следующим образом: выбирается случайная вершина <tex>v</tex> из левой доли графа (для этого требуется <tex>k</tex> случайных битов); затем исходный алгоритм <tex>A</tex> последовательно запускается на всех <tex>d</tex> наборах случайных битов, соответствующих соседям вершины <tex>v</tex>. Если все полученные ответы равны <tex>1</tex>, новый алгоритм также возвращает единицу; в противном случае возвращается ноль.
+
Пусть исходный алгоритм использует <tex>k = k(n)</tex> случайных битов для вычислений на входах длины <tex>n</tex>. Зафиксируем <tex>(2^k, 2^k, d)</tex> - экспандер <tex>G</tex>, где <tex>d > \cfrac{1}{\epsilon}</tex>. Новый алгоритм действует следующим образом: выбирается случайная вершина <tex>v</tex> из левой доли графа (для этого требуется <tex>k</tex> случайных битов); затем исходный алгоритм <tex>A</tex> последовательно запускается на всех <tex>d</tex> наборах случайных битов, соответствующих соседям вершины <tex>v</tex>. Если все полученные ответы равны <tex>1</tex>, новый алгоритм также возвращает единицу; в противном случае возвращается ноль.
Покажем, что у нового алгоритма вероятность ошибки не превосходит <tex>1/d</tex>. В самом деле, обозначим <tex>B = B(x)</tex> множество таких вершин <tex>w</tex> из правой доли графа, которые соответствуют неверному ответу старого алгоритма на входе <tex>x</tex>; аналогично, обозначим <tex>S = S(x)</tex> множество таких вершин v из левой доли графа, которые для которых новый алгоритм даёт неверный ответ на входе <tex>x</tex>. Очевидно, <tex>S</tex> состоит из вершин, все соседи которых лежат в B. Предположим, что <tex>S</tex> содержит не менее <tex>n/(1000d)</tex> вершин. Выберем среди них ровно <tex>n/(1000d)</tex> вершин и назовём это множество <tex>S'</tex>. По свойству экспандера, имеем
+
Покажем, что у нового алгоритма вероятность ошибки не превосходит <tex>\cfrac{1}{d}</tex>. В самом деле, обозначим <tex>B = B(x)</tex> множество таких вершин <tex>w</tex> из правой доли графа, которые соответствуют неверному ответу старого алгоритма на входе <tex>x</tex>; аналогично, обозначим <tex>S = S(x)</tex> множество таких вершин v из левой доли графа, которые для которых новый алгоритм даёт неверный ответ на входе <tex>x</tex>. Очевидно, <tex>S</tex> состоит из вершин, все соседи которых лежат в <tex>B</tex>. Предположим, что <tex>S</tex> содержит не менее <tex>\cfrac{n}{1000d}</tex> вершин. Выберем среди них ровно <tex>\cfrac{n}{1000d}</tex> вершин и назовём это множество <tex>S'</tex>. По свойству экспандера, имеем
  
<tex>|\Gamma(S')| \geqslant  \frac{7}{8}d\frac{n}{1000d}=7n/8000 > n/2000</tex>
+
<tex>|\Gamma(S')| \geqslant  \cfrac{7nd}{8 \cdot 1000d} = \cfrac{7n}{8000} > \cfrac{n}{2000}</tex>
  
 
Это противоречит тому, что все соседи <tex>S'</tex> лежат в <tex>B</tex>. В данном случае нам нужна явная в более сильном (чем в первом примере) смысле конструкция экспандера. Размер графа экспоненциално растёт с увеличенем <tex>k</tex>, и нам необходим алгоритм, который по заданному номеру вершины <tex>v</tex> (из левой доли графа) за время <tex>poly(k)</tex> находит список номеров всех соседей этой вершины (в правой доле графа).
 
Это противоречит тому, что все соседи <tex>S'</tex> лежат в <tex>B</tex>. В данном случае нам нужна явная в более сильном (чем в первом примере) смысле конструкция экспандера. Размер графа экспоненциално растёт с увеличенем <tex>k</tex>, и нам необходим алгоритм, который по заданному номеру вершины <tex>v</tex> (из левой доли графа) за время <tex>poly(k)</tex> находит список номеров всех соседей этой вершины (в правой доле графа).
  
 
===Хранение множества со сверхбыстрым запросом элементов===
 
===Хранение множества со сверхбыстрым запросом элементов===
Мы организуем хранение m-элементного множества <tex>S \subset \{1, . . . , n\}</tex> в виде описания <tex>X</tex>, состоящего из <tex>O(m log n)</tex> битов. При этом проверка принадлежности <tex>a \in S</tex> будет производиться чрезвычайно быстро. А именно, мы построим такой вероятностный алгоритм, который по любому входу <tex>a</tex> запрашивает из <tex>X</tex> один бит; если этот бит оказывается равным единице, то алгоритм отвечает, что <tex>a</tex> является элементом <tex>S</tex>; в противном случае алгоритм говорит, что <tex>a</tex> множеству не принадлежит. При этом для каждого <tex>a \in \{1, . . . , n\}</tex> алгоритм ошибается с вероятностью не более <tex>1/3</tex>.
+
Мы организуем хранение m-элементного множества <tex>S \subset \{1, \ldots , n\}</tex> в виде описания <tex>X</tex>, состоящего из <tex>O(m log n)</tex> битов. При этом проверка принадлежности <tex>a \in S</tex> будет производиться чрезвычайно быстро. А именно, мы построим такой вероятностный алгоритм, который по любому входу <tex>a</tex> запрашивает из <tex>X</tex> один бит; если этот бит оказывается равным единице, то алгоритм отвечает, что <tex>a</tex> является элементом <tex>S</tex>; в противном случае алгоритм говорит, что <tex>a</tex> множеству не принадлежит. При этом для каждого <tex>a \in \{1, \ldots , n\}</tex> алгоритм ошибается с вероятностью не более <tex>\cfrac{1}{3}</tex>.
  
 
Чтобы построить нужное нам хранилище <tex>X</tex>, мы сначала зафиксируем некоторый экспандер, у которого левая доля <tex>L</tex> состоит из <tex>n</tex> вершин, правая <tex>R</tex> из <tex>k = O(m log n)</tex> вершин, степень всех вершин левой доли одинакова и равна некоторому <tex>d</tex>, и для каждого <tex>A \subset L</tex> размера не более <tex>2m</tex>  
 
Чтобы построить нужное нам хранилище <tex>X</tex>, мы сначала зафиксируем некоторый экспандер, у которого левая доля <tex>L</tex> состоит из <tex>n</tex> вершин, правая <tex>R</tex> из <tex>k = O(m log n)</tex> вершин, степень всех вершин левой доли одинакова и равна некоторому <tex>d</tex>, и для каждого <tex>A \subset L</tex> размера не более <tex>2m</tex>  
  
<tex>|\Gamma(A)| \geqslant \frac{7}{8}d|A|</tex>
+
<tex>|\Gamma(A)| \geqslant \cfrac{7d|A|}{8}</tex>
  
<tex>X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены нулями.<tex>X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены нулями.
+
<tex>X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>\cfrac{2}{3}</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>\cfrac{2}{3}</tex> соседей были помечены нулями. <tex>X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>\cfrac{2}{3}</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>\cfrac{2}{3}</tex> соседей были помечены нулями.
  
Остаётся объяснить, как построить нужную нам разметку правой доли графа. Будем строить её последовательными приближениями. Сначала пометим всех соседей всех вершин из <tex>S</tex> единицами, а все остальные вершины – нулями. На данной разметке наш алгоритм с вероятностью <tex>1</tex> возвращает правильный ответ для всех <tex>a \in S</tex>. Однако для <tex>a</tex> не из <tex>S</tex> проверочный алгоритм может работать неверно. Обозначим T множество всех таких вершин вне <tex>S</tex>, у которых более <tex>d/3</tex> соседей помечены единицей. Поменяем разметку: пометим всех соседей <tex>T</tex> нулём. Теперь разметка может стать плохой для части вершин из <tex>S</tex>. Обозначим <tex>S'</tex> множество всех таких вершин из <tex>S</tex>, у которых более <tex>d/3</tex> соседей помечены нулями. Далее, поменяем разметку у
+
Остаётся объяснить, как построить нужную нам разметку правой доли графа. Будем строить её последовательными приближениями. Сначала пометим всех соседей всех вершин из <tex>S</tex> единицами, а все остальные вершины – нулями. На данной разметке наш алгоритм с вероятностью <tex>1</tex> возвращает правильный ответ для всех <tex>a \in S</tex>. Однако для <tex>a</tex> не из <tex>S</tex> проверочный алгоритм может работать неверно. Обозначим T множество всех таких вершин вне <tex>S</tex>, у которых более <tex>\cfrac{d}{3}</tex> соседей помечены единицей. Поменяем разметку: пометим всех соседей <tex>T</tex> нулём. Теперь разметка может стать плохой для части вершин из <tex>S</tex>. Обозначим <tex>S'</tex> множество всех таких вершин из <tex>S</tex>, у которых более <tex>\cfrac{d}{3}</tex> соседей помечены нулями. Далее, поменяем разметку у
 
всех соседей <tex>S'</tex> на единицы. После этого может вновь возникнуть множество ‘неправильных’ вершин вне <tex>S</tex>, и т.д.
 
всех соседей <tex>S'</tex> на единицы. После этого может вновь возникнуть множество ‘неправильных’ вершин вне <tex>S</tex>, и т.д.
  
 
Чтобы доказать, что данный процесс в конце концов сойдётся, нужно показать, что на каждом шаге число ‘проблемных’ вершин уменьшается в константу раз. Поскольку все шаги аналогичны, достаточно разобрать самый первый: докажем, что <tex>T</tex> в константу раз меньше, чем <tex>S</tex>. Мы воспользуемся тем, что для <tex>S \cup T</tex> выполнено свойство расширения:
 
Чтобы доказать, что данный процесс в конце концов сойдётся, нужно показать, что на каждом шаге число ‘проблемных’ вершин уменьшается в константу раз. Поскольку все шаги аналогичны, достаточно разобрать самый первый: докажем, что <tex>T</tex> в константу раз меньше, чем <tex>S</tex>. Мы воспользуемся тем, что для <tex>S \cup T</tex> выполнено свойство расширения:
  
<tex>(7/8)d(|S|+|T|) \leqslant |\Gamma(S \cup T)| \leqslant d|S| + (2/3)d|T|</tex>
+
<tex>\cfrac{7d}{8}(|S|+|T|) \leqslant |\Gamma(S \cup T)| \leqslant d|S| + \cfrac{2d|T|}{3}</tex>
  
Откуда получаем <tex>|T| \leqslant 3/5|S|</tex>.
+
Откуда получаем <tex>|T| \leqslant \cfrac{3|S|}{5}</tex>.
  
 
==Приложения и полезные свойства==
 
==Приложения и полезные свойства==
 
Первоначально интерес к экспандерам возник с целью построения устойчивой сети (телефонов или компьютеров) — число дуг графов расширения с ограниченным значением регулярности растет линейно по отношению к числу вершин.
 
Первоначально интерес к экспандерам возник с целью построения устойчивой сети (телефонов или компьютеров) — число дуг графов расширения с ограниченным значением регулярности растет линейно по отношению к числу вершин.
  
Экспандеры нашли широкое применение в теории вычислительных машин и систем, для построения алгоритмов, в корректирующих кодах, экстракторах, генераторах псевдослучайных чисел, сетях сортировки и компьютерных сетях. Они также используются для доказательства многих важных результатов в теории вычислительной сложности, таких как <tex>SL=L</tex> и Теорема PCP. В криптографии экспандеры используются для создания хеш-функций.
+
Экспандеры нашли широкое применение в теории вычислительных машин и систем, для построения алгоритмов, в корректирующих кодах<ref>[[wikipedia:Expander_code|Wikipedia {{---}} корректирующие коды]]</ref>, экстракторах, генераторах псевдослучайных чисел<ref>[[wikipedia:Pseudorandom_number_generator|Wikipedia {{---}} генератор псевдослучайных чисел]]</ref>, сетях сортировки<ref>[[wikipedia:Sorting_network|Wikipedia {{---}} Сеть сортировки]]</ref> и компьютерных сетях<ref>[[wikipedia:Computer_network|Wikipedia {{---}} компьютерные сети]]</ref>. Они также используются для доказательства многих важных результатов в теории вычислительной сложности, таких как ''SL''<ref>[[wikipedia:SL_(complexity)|Wikipedia {{---}} SL complexity]]</ref>=''L''<ref>Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291</ref> и [[PCP-теорема|Теорема PCP]]. В криптографии экспандеры используются для создания [[Универсальное семейство хеш-функций|хеш-функций]].
  
Ниже приведены некоторые свойства экспандеров, считающиеся полезными во многих областях.
 
 
===Лемма о перемешивании===
 
===Лемма о перемешивании===
Лемма о перемешивании утверждает, что для любых двух подмножеств вершин <tex>S,T\subseteq V</tex> число рёбер между <tex>S</tex> и <tex>T</tex> примерно равно числу рёбер в случайном <tex>d</tex>-регулярном графе. Приближение тем лучше, чем меньше <tex>\lambda =\max\{|\lambda _{2}|</tex>,<tex>|\lambda _{n}|\}</tex>. В случайном <tex>d<tex/>-регулярном графе, также как и в случайном графе Эрдёша — Реньи с вероятностью <tex>{\tfrac {d}{n}}</tex> выбора ребра, ожидается <tex>{\tfrac {d}{n}}\cdot |S|\cdot |T|</tex> рёбер между S и T.
+
Лемма о перемешивании утверждает, что для любых двух подмножеств вершин <tex>S,T\subseteq V</tex> число рёбер между <tex>S</tex> и <tex>T</tex> примерно равно числу рёбер в случайном <tex>d</tex>-регулярном графе. Приближение тем лучше, чем меньше <tex>\lambda =\max\{|\lambda _{2}|</tex>,<tex>|\lambda _{n}|\}</tex>. В случайном <tex>d</tex>-регулярном графе, также как и в случайном графе Эрдёша — Реньи<ref>[[wikipedia:Erdős–Rényi model|Wikipedia {{---}} Erdős–Rényi model]]</ref> с вероятностью <tex>{\cfrac {d}{n}}</tex> выбора ребра, ожидается <tex>{\cfrac {d}{n}}\cdot |S|\cdot |T|</tex> рёбер между <tex>S</tex> и <tex>T</tex>.
  
 
Более формально, пусть <tex>E(S, T)</tex> обозначает число рёбер между <tex>S</tex> и <tex>T</tex>. Если эти два множества пересекаются, дуги в пересечении считаются дважды, так что
 
Более формально, пусть <tex>E(S, T)</tex> обозначает число рёбер между <tex>S</tex> и <tex>T</tex>. Если эти два множества пересекаются, дуги в пересечении считаются дважды, так что
Строка 122: Строка 229:
 
Лемма о перемешивании утверждает, что
 
Лемма о перемешивании утверждает, что
  
<tex>\left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq d\lambda {\sqrt {|S|\cdot |T|}}</tex>,
+
<tex>\left|E(S,T)-{\cfrac {d\cdot |S|\cdot |T|}{n}}\right|\leqslant d\lambda {\sqrt {|S|\cdot |T|}}</tex>,
 
где <tex>\lambda </tex> — абсолютное значение нормализованного второго по величине собственного значения.
 
где <tex>\lambda </tex> — абсолютное значение нормализованного второго по величине собственного значения.
  
Недавно Билу (Bilu) и Линайл (Linial) показали, что обратное тоже верно, то есть, при условии выполнения неравенства из леммы второе по величине собственное значение равно <tex>O(d\lambda \cdot (1+\log(1/\lambda )))</tex>.
+
Недавно Билу и Линайл показали, что обратное тоже верно, то есть, при условии выполнения неравенства из леммы второе по величине собственное значение равно <tex>O(d\lambda \cdot (1+\log(\tfrac{1}{\lambda})))</tex><ref>[[http://www.cs.huji.ac.il/~nati/PAPERS/raman_lift.pdf|Lifts, discrepancy and nearly optimal spectral gap]]</ref>.
 +
 
 
===Блуждания по экспандеру===
 
===Блуждания по экспандеру===
Согласно границе Чернова, если выбирать много независимых случайных значений из интервала <tex>[−1, 1]</tex>, с большой степенью вероятности среднее выбранных значений будет близко к математическому ожиданию случайной переменной. Лемма о блуждании по экспандеру, согласно статьям Аджтари, Комлоша и Семереди и Гилмана, утверждает, что то же самое верно и для блужданий по экспандеру. Это полезно в теории дерандомизации, поскольку блуждание по экспандеру использует много меньше случайных бит, чем случайная независимая выборка.
+
Согласно границе Чернова<ref>[[wikipedia:Chernoff_bound|Wikipedia {{---}} граница Чернова]]</ref>, если выбирать много независимых случайных значений из интервала <tex>[-1, 1]</tex>, с большой степенью вероятности среднее выбранных значений будет близко к [[Математическое ожидание случайной величины|математическому ожиданию]] случайной переменной. Лемма о блуждании по экспандеру, согласно статьям Аджтари, Комлоша и Семереди<ref>M. Ajtai,J. Komlós,E. Szemerédi Proceedings of the 19th Annual ACM Symposium on Theory of Computing // ACM. — 1987. — С. 132–140. — ISBN 0-89791-221-7. — DOI:10.1145/28395.28410</ref> и Гилмана<ref>D. Gillman A Chernoff Bound for Random Walks on Expander Graphs // SIAM Journal on Computing. — Society for Industrial and Applied Mathematics, 1998. — Т. 27, вып. 4,. — С. 1203–1220. — DOI:10.1137/S0097539794268765</ref>, утверждает, что то же самое верно и для блужданий по экспандеру. Это полезно в теории дерандомизации<ref>[[wikipedia:Randomized_algorithm|Wikipedia {{---}} теория дерандомизации]]</ref>, поскольку блуждание по экспандеру использует много меньше случайных бит, чем случайная независимая выборка.
 +
 
 +
== См. также ==
 +
* [[Основные определения теории графов]]
 +
* [[Алгебра]]
 +
 
 +
==Примечания==
 +
 
 +
<references />
  
 
==Источники информации==
 
==Источники информации==
 
*[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D0%BF%D0%B0%D0%BD%D0%B4%D0%B5%D1%80_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2) Экспандер (теория графов)]
 
*[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D0%BF%D0%B0%D0%BD%D0%B4%D0%B5%D1%80_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2) Экспандер (теория графов)]
 +
*[https://compsciclub.ru/courses/expanders/2017-spring/classes/ Экспандеры и их применения (курс CS club)]
 +
*[https://compsciclub.ru/media/course_class_attachments/expanders-notes-spb-appendix.pdf Приложение к лекциям об экспандерах (CS club)]
 +
*[https://www.mccme.ru/~anromash/courses/expanders-notes-2014.pdf Экспандеры: конструкции и приложения]
 +
*[https://www.mccme.ru/~anromash/courses/expanders2009.pdf Определения и несколько примеров применений]
 +
*[http://www.tcs.tifr.res.in/~prahladh/teaching/05spring/ Expanders in Computer Science]
 +
*[http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf S. Hoory, N. Linial, A. Wigderson. Expander graphs and their applications. Bulletin of the AMS, vol. 43, Number 4, Oct. 2006, pp.439 561.]
 +
*[ H. Buhrman, P.B. Miltersen, J. Radhakrishnan, S. Venkatesh. Are Bitvectors optimal? SIAM J. Comput., 31(6):1723–1744, 2002.]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Основные определения теории графов]]

Текущая версия на 19:29, 4 сентября 2022

Определение:
Граф-экспандер (или расширяющийся граф, англ. expander graph) — в комбинаторике сильно разреженный граф, при этом связность определяется по вершинам, дугам или спектру. Это конечный ненаправленный мультиграф, в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность.


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

Основные определения

Определение:
Множество соседей (англ. set of neighbors) для множества вершин [math]S[/math] называется [math]\Gamma(S) = \{v: \exists w \in S:\ (v, w) \in E\}[/math].

Замечание: в графе могут присутствовать кратные ребра и петли. Если у каждой вершины есть петли, то [math]\forall S: S \supseteq \Gamma(S)[/math].

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

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

[math]h_{out}(G) = \min\limits_{0 \lt |S|\leqslant \cfrac{n}{2}} \cfrac{|\Gamma_{\text{out}}(S)|}{|S|}[/math],

где [math]\Gamma_{\text{out}}(S)[/math]внешняя граница [math]S[/math], то есть множество вершин из [math]V(G)\setminus S[/math], имеющих как минимум одного соседа в [math]S[/math].

[math]\Gamma_{\text{out}}(S) = \{v \in V(G) \diagdown S: \exists w \in S (v, w) \in E\}[/math].

Вершинное изопериметрическое число [math]h_{in}(G)[/math] графа [math]G[/math] определяется как

[math]h_{in}(G) = \min\limits_{0 \lt |S|\leqslant \cfrac{n}{2}} \cfrac{|\Gamma_{\text{in}}(S)|}{|S|}[/math],


где [math]\Gamma_{in}(S)[/math]внутренняя граница [math]S[/math], то есть множество вершин [math]S[/math], имеющих как минимум одного соседа в [math]V(G)\setminus S[/math].

[math]\Gamma_{in}(S) = \Gamma(S) \diagdown \Gamma_{in}(S)[/math]

Однородный (комбинаторный) экспандер

Определение:
Однородный (комбинаторный) экспандер (англ. combinatorial expander) называется граф [math]G = (V, E)[/math] с параметрами [math](n, d, \epsilon) \ (n = |V|[/math], d — степень каждой вершины, константа [math]\epsilon \lt 1)[/math], если выполняется условие: для [math]\ \forall S: S \subseteq V, \ |S| \leqslant \cfrac{n}{2} \ \ \exists \ \Gamma(S)[/math], которое достаточно велико, то есть [math]|\Gamma(S)| \gt (1 + \epsilon)|S|[/math].

Замечание: чем больше [math]\epsilon[/math], тем сильнее свойство расширения.

Теорема:
Пусть [math]\epsilon[/math] — некоторое положительное число меньшее [math]1[/math]. Тогда для всех достаточно больших четных [math]d = d(\epsilon)[/math] и всех [math]n[/math] существует однородный (комбинаторный) экспандер с параметрами [math](n, d, \epsilon)[/math].
Доказательство:
[math]\triangleright[/math]

Мы выберем граф случайно и покажем, что с положительной (и даже довольно близкой к [math]1[/math]) вероятностью такой граф оказывается экспандером. Отсюда будет следовать, что экспандеры существуют.

Оценим вероятность того, что полученный в результате граф не является экспандером, если найдется множество вершин [math]S[/math] (состоящее из не более, чем [math]\cfrac{n}{2}[/math] вершин), все соседи которого лежат в некотором множестве [math]T[/math], состоящем из [math]\lfloor (1 + \epsilon)|S|\rfloor[/math] вершин.

Зафиксируем некоторые множества вершин [math]S[/math] и [math]T[/math]. Зафиксируем номер перестановки [math]\pi_{i}[/math]. Вероятность того, что для каждой вершины [math]v \in S[/math] второй конец ребра [math]\{v, pi_{i}(v)\}[/math] попадёт в [math]T[/math], равна

[math]\cfrac{|T|}{n} \cdot \cfrac{|T| - 1}{n - 1} \cdot \ldots \cdot \cfrac{|T| - |S| + 1}{n - |S| + 1} \leqslant \bigg(\cfrac{|T|}{n}\bigg)^{|S|}[/math].

Поскольку мы выбираем [math]\cfrac{d}{2}[/math] перестановок независимо, вероятность того, что данное событие произойдёт для всех [math]i[/math] не превосходит [math]\bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}}[/math]. Таким образом,

Вероятность, что свойство экспандерности графа нарушено небольше [math]\sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}}[/math], где суммирование происходит по всем множествам вершин [math]S[/math] размера не более [math]\cfrac{n}{2}[/math] и по всем множествам [math]T[/math] размера [math]\lfloor(1 + \epsilon)|S|\rfloor[/math].

Оценим сумму:

[math]\sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}} \leqslant \sum\limits_{s = 1}^{\tfrac{n}{2}} \dbinom{s}{n} \cdot \dbinom{(1 + \epsilon)s}{n} \cdot \bigg(\cfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd}{2}}[/math]. [math](1)[/math]

Каждый биномиальный коэффициент [math]\dbinom{k}{n}[/math] можно оценить сверху величиной [math]\bigg(\cfrac{ne}{k}\bigg)^{k}[/math]. Тогда

[math] \sum\limits_{s = 1}^{\tfrac{n}{2}} \bigg(\cfrac{ne}{s}\bigg)^{s} \cdot \bigg(\cfrac{ne}{(1 + \epsilon)s}\bigg)^{(1 + \epsilon)s} \cdot \bigg(\cfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd}{2}} =[/math]

[math]\sum\limits_{s = 1}^{\tfrac{n}{2}} \bigg[\bigg(\cfrac{s}{n}\bigg)^{\tfrac{d}{2} - 2 - \epsilon} \cdot (1 + \epsilon)^{\tfrac{d}{2}} \cdot \cfrac{e^{1 + \epsilon} }{(1 + \epsilon)^{1 + \epsilon} }\bigg]^s[/math]. [math](2)[/math]

Заметим, что [math]s \leqslant \cfrac{n}{2}[/math], а [math]1 + \epsilon \lt 2[/math]. Таким образом, можно подобрать такое

[math]d = d(\epsilon)[/math], чтобы выражение в квадратных скобках в правой части [math](2)[/math] было меньше [math]\cfrac{1}{2}[/math] при всех значениях [math]\epsilon[/math]. Следовательно, сумма [math](1)[/math] меньше единицы. Что означает, что с положительной вероятностью случайный граф является экспандером с параметрами [math](n, d, \epsilon)[/math].
[math]\triangleleft[/math]

Двудольный экспандер

Определение:
Двудольный экспандер (англ. Bipartite expander) называется двудольный граф [math]G = (L,\ R,\ E)\ (L[/math] и [math]R[/math] — вершины левой и правой доли соответственно, [math]E[/math] — ребра графа [math]G[/math]) с параметрами [math](n,\ m,\ d,\ e)\ (n = |L|,\ m = |R|,\ d[/math] - степень всех вершин в левой доле), если выполняется условие: для [math]\forall S: S \subseteq L \ |S| \leqslant k \ \ |\Gamma(S)| \gt (1 - \epsilon)d|S|[/math].

Замечание 1: чем меньше значение [math]\epsilon[/math] в данном определении, тем сильнее свойство расширения.

Замечание 2: в приложениях как правило используют двудольные экспандеры с [math]\epsilon \lt \cfrac{1}{2}[/math], а для применения в теории кодирования (для построения экспандерных кодов) часто требуются двудольные экспандеры с ещё меньшими значениями [math]\epsilon[/math].

Теорема:
Пусть [math]\epsilon[/math] — некоторое положительное число. Тогда для [math]\forall \ n[/math] и [math]k \leqslant n[/math] найдется [math]d = O(\log n)[/math] и [math]m = O(dk)[/math] такие, что [math]\exists[/math] двудольный экспандер с параметрами [math](n, m, d, k, \epsilon)[/math].
Доказательство:
[math]\triangleright[/math]

Выберем случайный граф, то есть для [math]\forall \ v \in L[/math] случайно и независимо выбираем [math]d[/math] соседей в [math]R[/math] (разрешаются кратные ребра). Покажем с большой вероятностью такой граф оказывается экспандером.

Граф не является экспандером, если [math]\exists T \subset R: \ |T| = (1 - \epsilon)d|S|[/math] и [math]\exists S \subset L: \ \Gamma(S) = T[/math].

Поскольку при случайном выборе графа мы приводим все [math]nd[/math] рёбер случайно и независимо, то для [math]\forall[/math] ребра вероятность того, что его правый конец окажется в фиксированном множестве [math]T[/math], равна [math]\cfrac{|T|}{m}[/math]. Следовательно, вероятность, что свойство экспандерности графа нарушено [math] \leqslant \ \sum\limits_{S, T}\bigg(\cfrac{|T|}{m}\bigg)^{sd}[/math],

где суммирование происходит по всем множествам [math]S \subset L \ |S| \leqslant k \ \forall T: T \subset R \ |T| = (1 - \epsilon)d|S| [/math]. Оценим данную сумму сверху:

[math]\sum\limits_{s = 1}^{k} \dbinom{s}{n} \* \dbinom{(1 - \epsilon)sd}{m} \* \bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}[/math].

Оценивая биномиальные коэффициенты, получаем, что сумма не превосходит

[math] \sum\limits_{s = 1}^{k} \bigg(\cfrac{ne}{s}\bigg)^{s} \cdot \bigg(\cfrac{me}{(1 - \epsilon)sd}\bigg)^{(1 - \epsilon)sd} \cdot \bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd} \leqslant [/math]

[math]\sum\limits_{s = 1}^{k} \bigg[\cfrac{ne}{s} \cdot \bigg(\cfrac{e^{\tfrac{1 - \epsilon}{\epsilon}} \cdot (1 - \epsilon)sd}{m}\bigg)^{\epsilon d}\bigg]^{s} [/math].

Положим [math]m = Const * kd[/math] (с достаточно большим значением [math]Const[/math]), чтобы для всех возможных s выполнялось неравенство [math]\cfrac{e^{\tfrac{1 - \epsilon}{\epsilon}} \cdot (1 - \epsilon)sd}{m} \leqslant \cfrac{1}{2}[/math]. Тогда выражение в квадратных скобках не превосходит [math]\cfrac{ne}{2 ^ {\epsilon d}}[/math]. Остаётся выбрать [math]d \gt \cfrac{1}{\epsilon}\log(2en)[/math], и мы получаем [math]\cfrac{ne}{2^{\epsilon d}} \lt \cfrac{1}{2}[/math].

Таким образом, для выбранных значений параметров сумм не превосходят [math]1[/math]. Это означает, что с положительной вероятностью случайный двудольный граф является экспандером c параметрами [math](n, \ m, \ k, \ d, \ \epsilon)[/math].
[math]\triangleleft[/math]

Замечание: константы в [math]O[/math] зависят от [math]\epsilon[/math].

Теорема о паросочетаниях

Теорема:
Пусть [math]G[/math]двудольный граф. [math]G[/math] имеет совершенное паросочетание тогда и только тогда, когда [math]\forall S: S \supseteq L \ |S| \leqslant \Gamma(S)[/math].
Доказательство:
[math]\triangleright[/math]

Будем доказывать по индукции

Для [math]|L| = 1[/math] очевидно

Предположим, что верно для [math]L: |L| \lt m[/math]

Рассмотрим два случая:

  1. [math]\forall S: S \supseteq L, |S| \neq 0[/math] строго расширяется, то есть [math]|\Gamma(S)| \gt |S|[/math]. Выберем [math]\forall x: x \supset V(L) : (x, y) \in E[/math]. Тогда рассмотрим двудольный граф [math]G^{*}[/math], у которого левая доля [math]L^{*} = L \diagdown {x}[/math], а правая [math]R^{*} = R \diagdown {y}[/math]. Так как [math]\forall S: S \supset L[/math] удовлетворяет строгому неравенству теоремы, то каждое подмножество [math]L^{*}[/math] удовлетворяет неравенству, поскольку только одна вершина [math]y[/math] была удалена из [math]R[/math]. Следовательно, по предположению индукции меньший граф [math]G^{*}[/math] имеет паросочетание. К этому паросочетанию добавляем ребро (x, y) что дает совершенное паросочетание.
  2. Пусть [math]\exists\ T \in L, \ |T| \neq 0[/math] такое, что [math]|\Gamma(T)| = |T|[/math]. Рассмотрим порожденные графы [math]G_{1} = T \cup \Gamma(T)[/math] и [math]G_{2} = L \diagdown T \cup R \diagdown \Gamma(T)[/math]. По предположению индукции [math]G_{1}[/math] имеет совершенное паросочетание (Заметим, что предположение индукции не может использовано непосредственно на [math]G_{2}[/math]). Пусть [math]S \supseteq L \diagdown T[/math], тогда: [math]\Gamma_{G_{2}}(S) = \Gamma_{G}(S \cup T) \diagdown \Gamma_{G}(T) \ \Rightarrow[/math] [math]|\Gamma_{G_{2}}| \geqslant |S \cup T| - |T| = |S|[/math] Неравенство верно, поскольку [math]S \cup T[/math] удовлетворяет [math]|\Gamma_{G}(S \cup T)| \geqslant |S \cup T|[/math] и по предположению [math]|\Gamma_{G}(T)| = |T|[/math]. Следовательно, [math]G_{2}[/math] также удовлетворяет неравенству теоремы и по предположению индукции имеет паросочетание. Объединение совершенных паросочетаний [math]G_{1}[/math] и [math]G_{2}[/math] — паросочетание для [math]G[/math].
[math]\triangleleft[/math]

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

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

[math]h(G) = \min\limits_{0 \lt |S|\leqslant \cfrac{n}{2}} \cfrac{|\partial_{\text{out}}(S)|}{|S|}[/math],

где минимум берётся по всем непустым множествам [math]S[/math] не более чем [math]\cfrac{n}{2}[/math] вершин и [math]\partial(S)[/math]граничные дуги множества [math]S[/math], то есть, множество дуг с единственной вершиной в [math]S[/math].

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

Если [math]G[/math] является d-регулярным, возможно определение в терминах линейной алгебры на основе собственных значений матрицы смежности [math]A = A(G)[/math] графа [math]G[/math], где [math]A_{ij}[/math] — число дуг между вершинами [math]i[/math] и [math]j[/math]. Поскольку [math]A[/math] является симметричной, согласно спектральной теореме[2], [math]A[/math] имеет [math]n[/math] действительных собственных значений [math]\lambda_{1} \ge \lambda_{2} \ge \cdots \ge \lambda_{n}[/math]. Известно, что эти значения лежат в промежутке [math][-d, d][/math]. Граф регулярен тогда и только тогда, когда вектор [math]u\in \mathbb {R} ^{n}[/math] с [math]u_{i}=1[/math] для всех [math]i = 1 \ldots n[/math] является собственным вектором матрицы [math]A[/math], а его собственное число будет постоянной степенью графа. Таким образом, мы имеем [math]Au = du[/math], и [math]u[/math] — собственный вектор матрицы [math]A[/math] с собственными значениями [math]\lambda_{1} = d[/math], где [math]d[/math] — степень вершин графа [math]G[/math]. Спектральный зазор графа [math]G[/math] определяется как [math]d-\lambda_{2}[/math] и является мерилом спектрального расширения графа [math]G[/math].

Известно, что [math]\lambda_{n} = -d[/math] тогда и только тогда, когда [math]G[/math]двудольный. Во многих случаях, например в лемме о перемешивании, необходимо ограничить снизу не только зазор между [math]\lambda_{1}[/math] и [math]\lambda_{2}[/math], но и зазор между [math]\lambda_{1}[/math] и вторым максимальным по модулю собственным значением:

[math]\lambda=\max\{|\lambda_{2}|, |\lambda_{n}|\}[/math]

Поскольку это собственное значение соответствует некоторому собственному вектору, ортогональному [math]u[/math], его можно определить, используя отношение Рэлея: [math]\lambda=\max\limits_{0\neq v\perp u} \cfrac{\|Av\|_2}{\|v\|_2},[/math]

где [math]\|v\|_2=\left(\sum\limits_{i=1}^{n} v_i^2\right)^{\tfrac{1}{2}}[/math] — евклидова норма вектора [math]v\in \mathbb {R} ^{n}[/math].

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

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

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

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

Алгебраическое конструирование, основанное на графах Кэли[3], известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером и Галилом [4].

В качестве множества вершин графа возьмём [math]V = \mathbb Z _{n}\times \mathbb {Z} _{n}[/math] (таким образом, граф будет содержать [math]n^{2}[/math] вершин). Каждая вершина [math](x, y)[/math] из [math]\mathbb Z _{n}\times \mathbb {Z} _{n}[/math] соединяется рёбрами со следующими восьмую вершинами:

[math](x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).[/math]

(все арифметические вычисления производятся по модулю [math]n[/math]). Таким образом, степень каждой вершины графа равна 8. При достаточно больших [math]n[/math] в этом графе не будет кратных рёбер.

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

Теорема:
[math]\forall n[/math] граф [math]G_{n}[/math] второе по величине собственное число удовлетворяет неравенству [math]\lambda(G)\leqslant 5 \sqrt{2}[/math].

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

Теорема:
d-регулярный граф называется графом Рамануджана, если его второе по модулю собственное число [math] \lambda \leqslant 2\sqrt {d-1} - o(1)[/math].

Замечание: случайный d-регулярный граф с [math]n[/math] вершинами почти является графом Рамануджана, так как выполняется неравенство [math] \lambda \leqslant 2\sqrt {d-1} + \epsilon[/math] с вероятностью [math]1 - o(1)[/math] при [math]n \to \inf[/math].

Примеры применения экспандеров

Коды, исправляющие ошибки

С помощью расширяющего графа можно посторить линейный код, позволяющий исправлять ошибки в доле [math]\delta = \cfrac{1}{2000d}[/math] битов. Чтобы задать линейный код с длиной кодового слова n, достаточно описать его проверочную матрицу [math]H[/math] [math]([/math]слово [math]x \in \{0, 1\}^n[/math] является кодовым словом если и только если [math]Hx^t = 0)[/math]. Другими словами, нужно задать систему линейных уравнений для переменных [math]x_1, \ldots , x_n[/math] решения этой системы и будут кодовыми словами.

Увеличение вероятности успеха в алгоритмах с датчиком случайных чисел

Покажем, что для любого [math]\epsilon \gt 0[/math] полиномиальный вероятностный алгоритм A можно модифицировать таким образом, чтобы вероятность ошибки уменьшилась до [math]\epsilon[/math], а число используемых случайных битов не изменится.

Пусть исходный алгоритм использует [math]k = k(n)[/math] случайных битов для вычислений на входах длины [math]n[/math]. Зафиксируем [math](2^k, 2^k, d)[/math] - экспандер [math]G[/math], где [math]d \gt \cfrac{1}{\epsilon}[/math]. Новый алгоритм действует следующим образом: выбирается случайная вершина [math]v[/math] из левой доли графа (для этого требуется [math]k[/math] случайных битов); затем исходный алгоритм [math]A[/math] последовательно запускается на всех [math]d[/math] наборах случайных битов, соответствующих соседям вершины [math]v[/math]. Если все полученные ответы равны [math]1[/math], новый алгоритм также возвращает единицу; в противном случае возвращается ноль. Покажем, что у нового алгоритма вероятность ошибки не превосходит [math]\cfrac{1}{d}[/math]. В самом деле, обозначим [math]B = B(x)[/math] множество таких вершин [math]w[/math] из правой доли графа, которые соответствуют неверному ответу старого алгоритма на входе [math]x[/math]; аналогично, обозначим [math]S = S(x)[/math] множество таких вершин v из левой доли графа, которые для которых новый алгоритм даёт неверный ответ на входе [math]x[/math]. Очевидно, [math]S[/math] состоит из вершин, все соседи которых лежат в [math]B[/math]. Предположим, что [math]S[/math] содержит не менее [math]\cfrac{n}{1000d}[/math] вершин. Выберем среди них ровно [math]\cfrac{n}{1000d}[/math] вершин и назовём это множество [math]S'[/math]. По свойству экспандера, имеем

[math]|\Gamma(S')| \geqslant \cfrac{7nd}{8 \cdot 1000d} = \cfrac{7n}{8000} \gt \cfrac{n}{2000}[/math]

Это противоречит тому, что все соседи [math]S'[/math] лежат в [math]B[/math]. В данном случае нам нужна явная в более сильном (чем в первом примере) смысле конструкция экспандера. Размер графа экспоненциално растёт с увеличенем [math]k[/math], и нам необходим алгоритм, который по заданному номеру вершины [math]v[/math] (из левой доли графа) за время [math]poly(k)[/math] находит список номеров всех соседей этой вершины (в правой доле графа).

Хранение множества со сверхбыстрым запросом элементов

Мы организуем хранение m-элементного множества [math]S \subset \{1, \ldots , n\}[/math] в виде описания [math]X[/math], состоящего из [math]O(m log n)[/math] битов. При этом проверка принадлежности [math]a \in S[/math] будет производиться чрезвычайно быстро. А именно, мы построим такой вероятностный алгоритм, который по любому входу [math]a[/math] запрашивает из [math]X[/math] один бит; если этот бит оказывается равным единице, то алгоритм отвечает, что [math]a[/math] является элементом [math]S[/math]; в противном случае алгоритм говорит, что [math]a[/math] множеству не принадлежит. При этом для каждого [math]a \in \{1, \ldots , n\}[/math] алгоритм ошибается с вероятностью не более [math]\cfrac{1}{3}[/math].

Чтобы построить нужное нам хранилище [math]X[/math], мы сначала зафиксируем некоторый экспандер, у которого левая доля [math]L[/math] состоит из [math]n[/math] вершин, правая [math]R[/math] из [math]k = O(m log n)[/math] вершин, степень всех вершин левой доли одинакова и равна некоторому [math]d[/math], и для каждого [math]A \subset L[/math] размера не более [math]2m[/math]

[math]|\Gamma(A)| \geqslant \cfrac{7d|A|}{8}[/math]

[math]X[/math] будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из [math]S[/math] не менее [math]\cfrac{2}{3}[/math] соседей были помечены единицей, а у каждой вершины не из [math]S[/math] не менее [math]\cfrac{2}{3}[/math] соседей были помечены нулями. [math]X[/math] будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из [math]S[/math] не менее [math]\cfrac{2}{3}[/math] соседей были помечены единицей, а у каждой вершины не из [math]S[/math] не менее [math]\cfrac{2}{3}[/math] соседей были помечены нулями.

Остаётся объяснить, как построить нужную нам разметку правой доли графа. Будем строить её последовательными приближениями. Сначала пометим всех соседей всех вершин из [math]S[/math] единицами, а все остальные вершины – нулями. На данной разметке наш алгоритм с вероятностью [math]1[/math] возвращает правильный ответ для всех [math]a \in S[/math]. Однако для [math]a[/math] не из [math]S[/math] проверочный алгоритм может работать неверно. Обозначим T множество всех таких вершин вне [math]S[/math], у которых более [math]\cfrac{d}{3}[/math] соседей помечены единицей. Поменяем разметку: пометим всех соседей [math]T[/math] нулём. Теперь разметка может стать плохой для части вершин из [math]S[/math]. Обозначим [math]S'[/math] множество всех таких вершин из [math]S[/math], у которых более [math]\cfrac{d}{3}[/math] соседей помечены нулями. Далее, поменяем разметку у всех соседей [math]S'[/math] на единицы. После этого может вновь возникнуть множество ‘неправильных’ вершин вне [math]S[/math], и т.д.

Чтобы доказать, что данный процесс в конце концов сойдётся, нужно показать, что на каждом шаге число ‘проблемных’ вершин уменьшается в константу раз. Поскольку все шаги аналогичны, достаточно разобрать самый первый: докажем, что [math]T[/math] в константу раз меньше, чем [math]S[/math]. Мы воспользуемся тем, что для [math]S \cup T[/math] выполнено свойство расширения:

[math]\cfrac{7d}{8}(|S|+|T|) \leqslant |\Gamma(S \cup T)| \leqslant d|S| + \cfrac{2d|T|}{3}[/math]

Откуда получаем [math]|T| \leqslant \cfrac{3|S|}{5}[/math].

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

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

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

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

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

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

[math]E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S)[/math]. Лемма о перемешивании утверждает, что

[math]\left|E(S,T)-{\cfrac {d\cdot |S|\cdot |T|}{n}}\right|\leqslant d\lambda {\sqrt {|S|\cdot |T|}}[/math], где [math]\lambda [/math] — абсолютное значение нормализованного второго по величине собственного значения.

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

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

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

См. также

Примечания

  1. Wikipedia — константа Чигера
  2. Wikipedia — спектральная теорема
  3. Wikipedia — граф Кэли
  4. Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291
  5. Wikipedia — корректирующие коды
  6. Wikipedia — генератор псевдослучайных чисел
  7. Wikipedia — Сеть сортировки
  8. Wikipedia — компьютерные сети
  9. Wikipedia — SL complexity
  10. Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291
  11. Wikipedia — Erdős–Rényi model
  12. [discrepancy and nearly optimal spectral gap]
  13. Wikipedia — граница Чернова
  14. M. Ajtai,J. Komlós,E. Szemerédi Proceedings of the 19th Annual ACM Symposium on Theory of Computing // ACM. — 1987. — С. 132–140. — ISBN 0-89791-221-7. — DOI:10.1145/28395.28410
  15. D. Gillman A Chernoff Bound for Random Walks on Expander Graphs // SIAM Journal on Computing. — Society for Industrial and Applied Mathematics, 1998. — Т. 27, вып. 4,. — С. 1203–1220. — DOI:10.1137/S0097539794268765
  16. Wikipedia — теория дерандомизации

Источники информации