Изменения

{{Определение|definition='''Граф-экспандер ''' (или расширяющийся граф, англ. ''expander graph'') {{---}} в комбинаторике сильно разреженный [[Основные определения теории графов#Ориентированные графы|граф]], при этом связность определяется по вершинам, дугам или спектру. Это конечный ненаправленный ''мультиграф'', в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность. Различные формализации этих понятий дают различные типы экспандеров: [[Графы-экспандеры#Реберное расширение|рёберный расширитель]], [[Графы-экспандеры#Вершинное расширение|вершинный расширитель]], и [[Графы-экспандеры#Спектральное расширение|спектральный расширитель]].}}

'''Множество соседей ''' (англ. ''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>==== Однородный (комбинаторный) экспандер ====

'''Однородный (комбинаторный) экспандер''' (англ. ''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| \leq leqslant \cfrac{n/}{2 } \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.

Пусть <tex>\epsilon</tex> {{---}} некоторое положительное число меньшее <tex>1</tex>. Тогда для всех достаточно больших четных <tex>d = d(\epsilon)</tex> и всех <tex>n</tex> существует однородный (комбинаторный) экспандер с параметрами <tex>(n, d, \epsilon)</tex>.

Мы выберем граф случайно и покажем, что с положительной (и даже довольно близкой к <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>\fraccfrac{|T|}{n} \cdot \fraccfrac{|T| - 1}{n - 1} \cdot \ldots \cdot \fraccfrac{|T| - |S| + 1}{n - |S| + 1} \leq leqslant \bigg(\fraccfrac{|T|}{n}\bigg)^{|S|}</tex>.

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

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

<tex>\sum_sum\limits_{S, T}\bigg(\fraccfrac{|T|}{n}\bigg)^{(\tfrac{d/2)|S|}{2}} \leq leqslant \sum_sum\limits_{s = 1}^{\tfrac{n/}{2}}\binomdbinom{s}{n} \cdot \binomdbinom{(1 + \epsilon)s}{n} \cdot \bigg(\fraccfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd/}{2}}</tex>. <tex>(1)</tex>

Каждый биномиальный коэффициент <tex>\binomdbinom{k}{n}</tex> можно оценить сверху величиной <tex>\bigg(\fraccfrac{ne}{k}\bigg)^{k}</tex>. Тогда

\sum_sum\limits_{s = 1}^{\tfrac{n/}{2}} \bigg(\fraccfrac{ne}{s}\bigg)^{s} \cdot \bigg(\fraccfrac{ne}{(1 + \epsilon)s}\bigg)^{(1 + \epsilon)s} \cdot \bigg(\fraccfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd/}{2}} = </tex> <tex>\sum\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 \fraccfrac{e^{1 + \epsilon} }{(1 + \epsilon)^{1 + \epsilon} }\bigg]^s</tex>. <tex>(2)</tex>

Заметим, что <tex>s leq \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>.

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

'''Двудольный экспандер''' (англ. ''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| \leq leqslant k \ \ |\Gamma(S)| > (1 - \epsilon)d|S|</tex>.

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

Пусть <tex>\epsilon</tex> {{---}} некоторое положительное число. Тогда для <tex>\forall \ n</tex> и <tex>k \leq leqslant n</tex> найдется <tex>d = O(\log n)</tex> и <tex>m = O(dk)</tex> такие, что <tex>\exists</tex> двудольный экспандер с параметрами <tex>(n, m, d, k, \epsilon)</tex>.

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

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

<tex>\sum_sum\limits_{s = 1}^{k} \binomdbinom{s}{n} \* \binomdbinom{(1 - \epsilon)sd}{m} \* \bigg(\fraccfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}</tex>.

\sum_sum\limits_{s = 1}^{k} \bigg(\fraccfrac{ne}{s}\bigg)^{s} \cdot \bigg(\fraccfrac{me}{(1 - \epsilon)sd}\bigg)^{(1 - \epsilon)sd} \cdot \bigg(\fraccfrac{(1 - \epsilon)sd}{m}\bigg)^{sd} \leq leqslant </tex> <tex>\sum_sum\limits_{s = 1}^{k} \bigg[\fraccfrac{ne}{s} \cdot \bigg(\fraccfrac{e^{(\tfrac{1 - \epsilon)/}{\epsilon}} \cdot (1 - \epsilon)sd}{m}\bigg)^{\epsilon d}\bigg]^{s}

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

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

<tex>G</tex> имеет совершенное паросочетание тогда и только тогда, когда <tex>\forall S: S \supseteq L \ |S| \leq leqslant \Gamma(S)</tex>.

''Рёберное расширение'' (также ''изопериметрическое число'' или константа Чигера) <tex>h(G)</tex> графа <tex>G</tex> для <tex>n</tex> вершин определяется как <texref>h(G) = \min\limits_{0 < |S[[wikipedia:Cheeger_constant|\leqslant \fracWikipedia {n}{2}} \frac{|\partial_{\text{out}}(S)|---}{|S|}константа Чигера]]</tex>, где минимум берётся по всем непустым множествам <tex>S</tex> не более чем <tex>n/2</texref> вершин и <tex>\partial(S)</tex> — ''граничные дуги'' множества <tex>S</tex>, то есть, множество дуг с единственной вершиной в <tex>S</tex>. ===Вершинное расширение===''Вершинное изопериметрическое число'' <tex>h_{out}h(G)</tex> (также ''вершинное раширение'') графа <tex>G</tex> определяется как для <tex>h_{out}(G) = \min\limits_{0 < |S|\leqslant \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|}</tex>,вершин определяется как

где <tex>h(G) = \partial_min\limits_{0 < |S|\leqslant \textcfrac{n}{out2}}(S)</tex> — ''внешняя граница'' <tex>S</tex>, то есть множество вершин из <tex>V(G)\setminus S</tex>, имеющих как минимум одного соседа в <tex>S</tex>. В варианте этого определения (называемом ''уникальным соседним расширением'') <tex>cfrac{|\partial_{\text{out}}(S)</tex> заменяется на множество вершин из <tex>V</tex> с ''точностью одним'' соседом из <tex>|}{|S|}</tex>.,

''Вершинное изопериметрическое число'' где минимум берётся по всем непустым множествам <tex>h_{in}(G)</tex> графа <tex>GS</tex> определяется как не более чем <tex>h_{in}(G) = \min\limits_{0 < |S|\leqslant \fraccfrac{n}{2}} \frac{|\partial_{\text{in}}(S)|}{|S|}</tex>,  где вершин и <tex>\partial_{in}partial(S)</tex> — ''внутренняя границаграничные дуги'' множества <tex>S</tex>, то есть , множество вершин <tex>S</tex>, имеющих как минимум одного соседа дуг с единственной вершиной в <tex>V(G)\setminus 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> является симметричной, согласно спектральной теореме<ref>[[wikipedia:Spectral theorem|Wikipedia {{---}} спектральная теорема]]</ref>, <tex>A</tex> имеет <tex>n</tex> действительных собственных значений <tex>\lambda_1 lambda_{1} \ge \lambda_2 lambda_{2} \ge \cdots \ge \lambda_{n}</tex>. Известно, что эти значения лежат в промежутке <tex>[−d-d, d]</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>λ1 \lambda_{1} = d</tex>, где <tex>d</tex> — степень вершин графа <tex>G</tex>. Спектральный зазор графа <tex>G</tex> определяется как <tex>d−λ2d-\lambda_{2}</tex> и является мерилом спектрального расширения графа <tex>G</tex>.

Известно, что <tex>\lambda_n lambda_{n} = −d-d</tex> тогда и только тогда, когда <tex>G</tex> — {{---}} [[Двудольные графы|двудольный]]. Во многих случаях, например в [[Графы-экспандеры#Лемма о перемешивании|лемме о перемешивании]], необходимо ограничить снизу не только зазор между <tex>\lambda_1lambda_{1}</tex> и <tex>\lambda_2lambda_{2}</tex>, но и зазор между <tex>\lambda_1lambda_{1}</tex> и вторым максимальным по модулю собственным значением:

<tex>\lambda=\max\{|\lambda_2lambda_{2}|, |\lambda_{n}|\}</tex>

<tex>\lambda=\max_max\limits_{0\neq v\perp u} \fraccfrac{\|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>\|v\|_2=\left(\sum\limits_{i=1}^{n} v_i^2\right)^{\tfrac{1}{2}}</tex> {{---}} евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>. Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\tfrac cfrac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>−1</tex> и <tex>(-1, 1)</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения [[Матрица Кирхгофа|матрицы Кирхгофа]]. Для направленного графа используются сингулярные значения матрицы сопряжения <tex>A</tex>, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</tex>.

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

[[Алгебра|Алгебраическое ]] конструирование, основанное на графах Кэли<ref>[[wikipedia:Cayley_graph|Wikipedia {{---}} граф Кэли]]</ref>, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером (Gabber) и Галилом (Galil). Для любого натурального <texref>n<Omer Reingold Undirected connectivity in log-space //tex> строим графJournal of the ACM. — 2008. — Т. 55, <tex>G_{n}вып. 4. — DOI:10.1145/1391289.1391291</texref> со множеством .  В качестве множества вершин графа возьмём <tex>V = \mathbb Z _{n}\times \mathbb {Z} _{n}</tex>(таким образом, где граф будет содержать <tex>\mathbb n^{Z2} _{n}=\mathbb Z /n \mathbb Z</tex> вершин). Для любой вершины Каждая вершина <tex>(x,y)\in </tex> из <tex>\mathbb {Z} _{n}\times \mathbb {Z} _{n}</tex>, её восемь соседей будутсоединяется рёбрами со следующими восьмую вершинами:

Для всех <tex>\forall n</tex> граф <tex>GnG_{n}</tex> второе по величине собственное числоудовлетворяет неравенству

<tex>\lambda(G)\leq leqslant 5 \sqrt{2}</tex>.}}

<tex>{{Теорема|statement=[[Основные определения теории графов#Часто используемые графы|d</tex>-регулярный граф ]] называется графом Рамануджана, если его второе по модулю собственное число не превосходит <tex>\lambda \leqslant 2{\sqrt {d-1}}</tex>. Любоцкий, Сарнак, Филлипс и Маргулис указали явную конструкцию графов Кэли, являющихся графами Рамануджана. Опишем эту конструкцию.Пусть <tex>p</tex> и <tex>q</tex> простые числа, <tex>p = 1 \bmod 4</tex> и <tex>q = - o(1 \bmod 4</tex>. В качестве группы <tex>G</tex> возьмём <tex>PGL(2, \mathbb Z/q{\mathbb Z})</tex>, т.е. невырожденные матрицы 2 × 2 над полем вычетов по модулю <tex>q</tex>, профакторизованные по отношению пропорциональности (с обычной операцией матричного умножения).Далее мы зададим в этой группе симметричное множество <tex>S</tex>. Выберем такое целое <tex>i</tex>, что <tex>i^2 = −1 \bmod q</tex>. Можно доказать, что тогда имеется ровно <tex>(p + 1)</tex> целочисленное решение уравнения}}

'''Замечание:''' случайный [[Основные определения теории графов#Часто используемые графы|d-регулярный граф]] с <tex>a_0^2 + a_1^2 + a_3^2 = p</tex> такое, что <tex>a_0</tex> положительно и нечётно, а <tex>a_1n</tex>вершинами почти является графом Рамануджана, так как выполняется неравенство <tex>a_2</tex>, <tex>a_3</tex> чётны. Каждой такой четвёрке сопоставим матрицу <tex>A = \begin{pmatrix} a_0 + ia_1 & a_2 + ia_3lambda \leqslant 2\ sqrt {d-a_2 1} + ia_3 & a_0 - ia_1 \end{pmatrix}epsilon</tex> Эти матрицы образуют множество S.Нетрудно понять, что граф Кэли с вероятностью <tex>1 - o(G, S1)</tex> состоит из при <tex>n \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{to \sqrt{p}}inf</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> решения этой системы и будут кодовыми словами. 

Пусть исходный алгоритм использует <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>\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 \fraccfrac{77nd}{8\cdot 1000d}d= \fraccfrac{n7n}{1000d8000}=7n/8000 > \cfrac{n/}{2000}</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>|\Gamma(A)| \geqslant \fraccfrac{77d|A|}{8}d|A|</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>\cfrac{d/}{3}</tex> соседей помечены единицей. Поменяем разметку: пометим всех соседей <tex>T</tex> нулём. Теперь разметка может стать плохой для части вершин из <tex>S</tex>. Обозначим <tex>S'</tex> множество всех таких вершин из <tex>S</tex>, у которых более <tex>\cfrac{d/}{3}</tex> соседей помечены нулями. Далее, поменяем разметку у

<tex>(7/\cfrac{7d}{8)d}(|S|+|T|) \leqslant |\Gamma(S \cup T)| \leqslant d|S| + (2/3)d\cfrac{2d|T|}{3}</tex>

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

Экспандеры нашли широкое применение в теории вычислительных машин и систем, для построения алгоритмов, в корректирующих кодах<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''<texref>[[wikipedia:SL_(complexity)|Wikipedia {{---}} SLcomplexity]]</ref>=''L''<ref>Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291</texref> и [[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>-регулярном графе, также как и в случайном графе Эрдёша — Реньи <ref>[[wikipedia:Erdős–Rényi model|Wikipedia {{---}} Erdős–Rényi model]]</ref> с вероятностью <tex>{\tfrac cfrac {d}{n}}</tex> выбора ребра, ожидается <tex>{\tfrac cfrac {d}{n}}\cdot |S|\cdot |T|</tex> рёбер между <tex>S</tex> и <tex>T</tex>.

<tex>\left|E(S,T)-{\frac cfrac {d\cdot |S|\cdot |T|}{n}}\right|\leq leqslant d\lambda {\sqrt {|S|\cdot |T|}}</tex>,

Недавно Билу (Bilu) и Линайл (Linial) показали, что обратное тоже верно, то есть, при условии выполнения неравенства из леммы второе по величине собственное значение равно <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>.

Согласно границе Чернова<ref>[[wikipedia:Chernoff_bound|Wikipedia {{---}} граница Чернова]]</ref>, если выбирать много независимых случайных значений из интервала <tex>[−1-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://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/lectures/lec1.pdf лекции Синтии Дворка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.]