Изменения

{{Определение|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>h(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>\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>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>1</tex>. Это означает, что с положительной вероятностью случайный двудольный граф является экспандером c параметрами <tex>h(G) = n, \min_{0 < |S|m, \le k, \frac{n}{2}} \frac{|d, \partial_{\text{out}}(Sepsilon)|</tex>.}{|S|}'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>,.

где минимум берётся по всем непустым множествам ==== Теорема о паросочетаниях ===={{Теорема|statement=Пусть <tex>SG</tex> не более чем {{---}} [[Двудольные графы|двудольный граф]].<tex>n/2G</tex> вершин имеет совершенное паросочетание тогда и только тогда, когда <tex>\partialforall S: S \supseteq L \ |S| \leqslant \Gamma(S)</tex> — ''граничные дуги'' множества <tex>S</tex>, то есть, множество дуг с единственной вершиной в <tex>S</tex>.|proof=Будем доказывать по индукции

===Вершинное расширение===''Вершинное изопериметрическое число'' Для <tex>h_{out}(G)</tex> (также ''вершинное раширение'') графа <tex>G|L| = 1</tex> определяется какочевидно

Предположим, что верно для <tex>h_{out}(G) = \min_{0 < L: |SL|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|},< m</tex>

где Рассмотрим два случая:# <tex>\partial_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 \textdiagdown {outx}</tex>, а правая <tex>R^{*} = R \diagdown {y}(S)</tex> — ''внешняя граница'' . Так как <tex>\forall S: S \supset L</tex>удовлетворяет строгому неравенству теоремы, то есть множество вершин каждое подмножество <tex>L^{*}</tex> удовлетворяет неравенству, поскольку только одна вершина <tex>y</tex> была удалена из <tex>VR</tex>. Следовательно, по предположению индукции меньший граф <tex>G^{*}</tex> имеет паросочетание. К этому паросочетанию добавляем ребро (Gx, y)что дает совершенное паросочетание.# Пусть <tex>\setminus Sexists\ T \in L, \ |T| \neq 0</tex>такое, имеющих как минимум одного соседа в Sчто <tex>|\Gamma(T)| = |T|</tex>. В варианте этого определения Рассмотрим порожденные графы <tex>G_{1} = T \cup \Gamma(называемом ''уникальным соседним расширением''T) </tex>и <tex>G_{2} = L \diagdown T \cup R \partial_diagdown \Gamma(T)</tex>. По предположению индукции <tex>G_{1}</tex> имеет совершенное паросочетание (Заметим, что предположение индукции не может использовано непосредственно на <tex>G_{2}</tex>). Пусть <tex>S \textsupseteq L \diagdown T</tex>, тогда: <tex>\Gamma_{outG_{2}}(S)= \Gamma_{G}(S \cup T) \diagdown \Gamma_{G}(T) \ \Rightarrow</tex> заменяется на множество вершин из <tex>V|\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>.}}

===Реберное расширение===''Рёберное расширение'' (также ''Вершинное изопериметрическое число'' или константа Чигера<texref>h_[[wikipedia:Cheeger_constant|Wikipedia {in{---}} константа Чигера]]</ref>) <tex>h(G)</tex> графа <tex>G</tex> для <tex>n</tex> вершин определяется как

<tex>h_{in}h(G) = \min_min\limits_{0 < |S|\le leqslant \fraccfrac{n}{2}} \fraccfrac{|\partial_{\text{inout}}(S)|}{|S|},</tex>,

где минимум берётся по всем непустым множествам <tex>S</tex> не более чем <tex>∂_\cfrac{inn}{2}</tex> вершин и <tex>\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_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>.

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

[[Алгебра|Алгебраическое ]] конструирование, основанное на графах Кэли<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} - o(1)</tex>.}} '''Замечание:''' случайный [[Основные определения теории графов#Часто используемые графы|d-регулярный граф]] с <tex>n</tex> вершинами почти является графом Рамануджана, так как выполняется неравенство <tex> \lambda \leqslant 2\sqrt {d-1}+ \epsilon</tex> с вероятностью <tex>1 - o(1)</tex> при <tex>n \to \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>\epsilon > 0</tex> полиномиальный вероятностный алгоритм A можно модифицировать таким образом, чтобы вероятность ошибки уменьшилась до <tex>\epsilon</tex>, а число используемых случайных битов не изменится. Пусть исходный алгоритм использует <tex>pk = k(n)</tex> и случайных битов для вычислений на входах длины <tex>n</tex>. Зафиксируем <tex>(2^k, 2^k, d)</tex> - экспандер <tex>qG</tex> простые числа, где <tex>p = d > \cfrac{1}{\epsilon}</tex> . Новый алгоритм действует следующим образом: выбирается случайная вершина <tex>modv</tex> из левой доли графа (для этого требуется <tex>4k</tex> и случайных битов); затем исходный алгоритм <tex>A</tex> последовательно запускается на всех <tex>d</tex> наборах случайных битов, соответствующих соседям вершины <tex>q = 1v</tex> . Если все полученные ответы равны <tex>mod1</tex> , новый алгоритм также возвращает единицу; в противном случае возвращается ноль.Покажем, что у нового алгоритма вероятность ошибки не превосходит <tex>4\cfrac{1}{d}</tex>. В качестве группы самом деле, обозначим <tex>B = B(x)</tex>Gмножество таких вершин <tex>w</tex> из правой доли графа, которые соответствуют неверному ответу старого алгоритма на входе <tex>x</tex> возьмём ; аналогично, обозначим <tex>PGLS = S(2x)</tex> множество таких вершин v из левой доли графа, которые для которых новый алгоритм даёт неверный ответ на входе <tex>x</tex>. Очевидно, <tex>S</tex> состоит из вершин, все соседи которых лежат в <tex>B</tex>. Предположим, что <tex>S</tex> содержит не менее <tex>\cfrac{n}{1000d}</tex> вершин. Выберем среди них ровно <tex>\mathbb Zcfrac{n}{1000d}</qtex> вершин и назовём это множество <tex>S'</tex>. По свойству экспандера, имеем <tex>|\Gamma(S')| \geqslant \cfrac{7nd}{8 \cdot 1000d} = \cfrac{7n}{8000} > \mathbb Zcfrac{n}{2000})</tex> Это противоречит тому, тчто все соседи <tex>S'</tex> лежат в <tex>B</tex>.еВ данном случае нам нужна явная в более сильном (чем в первом примере) смысле конструкция экспандера. невырожденные матрицы 2 × 2 над полем вычетов по модулю Размер графа экспоненциално растёт с увеличенем <tex>qk</tex>, профакторизованные и нам необходим алгоритм, который по отношению пропорциональности заданному номеру вершины <tex>v</tex> (с обычной операцией матричного умноженияиз левой доли графа) за время <tex>poly(k)</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>iS</tex>; в противном случае алгоритм говорит, что <tex>i^2 = −1a</tex> множеству не принадлежит. При этом для каждого <tex>moda \in \{1, \ldots , n\}</tex> алгоритм ошибается с вероятностью не более <tex>q\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>|\Gamma(p + 1A)| \geqslant \cfrac{7d|A|}{8}</tex> целочисленное решение уравнения

<tex>a_0^X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>\cfrac{2}{3}</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>\cfrac{2 + a_1^}{3}</tex> соседей были помечены нулями. <tex>X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>\cfrac{2 + a_3^}{3}</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>\cfrac{2 = p}{3}</tex>соседей были помечены нулями.

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

Чтобы доказать, что данный процесс в конце концов сойдётся, нужно показать, что на каждом шаге число ‘проблемных’ вершин уменьшается в константу раз. Поскольку все шаги аналогичны, достаточно разобрать самый первый: докажем, что <tex>A = \begin{pmatrix} a_0 + ia_1 & a_2 + ia_3\\ -a_2 + ia_3 & a_0 - ia_1 T</tex> в константу раз меньше, чем <tex>S</tex>. Мы воспользуемся тем, что для <tex>S \end{pmatrix}cup T</tex>выполнено свойство расширения:

Эти матрицы образуют множество S.Нетрудно понять, что граф Кэли <tex>\cfrac{7d}{8}(G, |S|+|T|)</tex> состоит из <tex>\Thetaleqslant |\Gamma(q^3S \cup T)</tex> вершин, и степень каждой вершины равна <tex>(p | \leqslant d|S| + 1)</tex>. Свойства данного графа зависят от соотношения <tex>p</tex> и <tex>q</tex>. Рассмотрим случай, когда p является квадратичным вычетом по модулю <tex>q</tex>. Тогда полученный граф Кэли состоит из двух связных компонент (поскольку все матрицы из <tex>S</tex> лежат в подгруппе <tex>G</tex> индекса два — подгруппе матриц, определитель которых является квадратичным вычетом). Обозначим <tex>X^\cfrac{p,q2d|T|}</tex> связную компоненту полученного графа. Можно доказать, что у <tex>X^{p,q}</tex> второе по абсолютной величине собственное число не превосходит <tex>2{\sqrt{p}3}</tex>, т.е. мы получили граф Рамануджана.

==Применение экспандеров=====Коды, исправляющие ошибки===С помощью расширяющего графа можно посторить линейный код, позволяющий исправлять ошибки в доле Откуда получаем <tex>|T| \delta = 1/(2000d)</tex> битов. Чтобы задать линейный код с длиной кодового слова n, достаточно описать его проверочную матрицу <tex>H</tex> <tex>(</tex>слово <tex>x \in leqslant \cfrac{3|S|}{0, 1\5}^n</tex> является кодовым словом если и только если <tex>Hx^t = 0)</tex>. Другими словами, нужно задать систему линейных уравнений для переменных <tex>x_1, . . . , x_n;</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 />