Изменения

'''Однородный (комбинаторный) Граф-экспандер''' называется (или расширяющийся граф <tex>G = (V, Eангл. ''expander graph'')</tex> с параметрами <tex>(n, d, \epsilon) \ (n = {{---}} в комбинаторике сильно разреженный [[Основные определения теории графов#Ориентированные графы|V|</tex>граф]], d - степень каждой вершиныпри этом связность определяется по вершинам, константа <tex>\epsilon < 1)</tex>дугам или спектру. Это конечный ненаправленный ''мультиграф'', если выполняется условие: для <tex>\ \forall S \subseteq V \ \ |S| \leq n/2 \ \ \exists \</tex> множество соседей <tex>r(S) = \{v: \exists w \in Sв котором любое подмножество вершин,\ (vне являясь «слишком большим», w) \in E\}</tex>, которое достаточно велико, то есть <tex>|r(S)| > (1 + \epsilon)|S|</tex>имеет «сильную» связность.

'''Замечание 2:''' чем больше <tex>\epsilon</tex>Любой связный граф является экспандером, тем сильнее свойство расширенияоднако различные связные [[Основные определения теории графов#Ориентированные графы|графы]] имеют различные параметры расширителя. {{Теорема[[Основные определения теории графов#Часто используемые графы|statement=<tex>\forall n</tex>Полный граф]] имеет лучшие параметры расширителя, <tex>\forall \epsilon < 1</tex>для достаточно больших четных <tex>d = d(\epsilon)</tex> существует однородный(комбинаторный) экспандер с параметрами <tex>(nно имеет наибольшую возможную степень. Неформально говоря, dграф является хорошим экспандером, \epsilon)</tex>если он имеет низкую степень и высокий параметр расширителя.}}== Основные определения ==

'''Двудольный экспандерМножество соседей''' называется граф <tex>G = (L,\ R,\ Eангл. ''set of neighbors'')\ (Lдля множества вершин </tex> и <tex>RS</tex> - вершины левой и правой доле соответственно, <tex>E</tex> - ребра графа <tex>G</tex>) с параметрами называется <tex>\Gamma(n,\ m,\ d,\ eS)\ (n = |L|,\ m = |R|,\ d</tex> - степень всех вершин в левой доле), если выполняется условие{v: для <tex>\forall S exists w \subseteq L \ |in S| :\leq k \ \ |r(Sv, w)| > (1 - \epsilon)d|S|in E\}</tex>.

'''Замечание 1:''' чем меньше значение в графе могут присутствовать кратные ребра и петли. Если у каждой вершины есть петли, то <tex>\epsilonforall S: S \supseteq \Gamma(S)</tex> в данном определении, тем сильнее свойство расширения.

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

{{Теорема|statement=Пусть <tex>h_{out}(G) = \epsilonmin\limits_{0 </tex> - некоторое положительное число. Тогда для <tex>|S|\forall leqslant \ cfrac{n</tex> и <tex>k }{2}} \cfrac{|\leq n</tex> найдется <tex>d = O(Gamma_{\log n)</tex> и <tex>m = Otext{out}}(dkS)|}{|S|}</tex> такие, что <tex>\exists</tex> двудольный экспандер с параметрами <tex>(n, m, d, k, \epsilon)</tex>.

'''Замечание:''' константы в где <tex>O\Gamma_{\text{out}}(S)</tex> зависят от — ''внешняя граница'' <tex>\epsilonS</tex>.|proof=Выберем случайный граф, то есть для множество вершин из <tex>V(G)\forall \ v \in Lsetminus S</tex> случайно и независимо выбираем <tex>d</tex> соседей , имеющих как минимум одного соседа в <tex>RS</tex> (разрешаются кратные ребра). Покажем с большой вероятностью такой граф оказывается экспандером.

Граф не является экспандером, если <tex>\exists T Gamma_{\text{out}}(S) = \subset R {v \ |T| = in V(1 - G) \epsilon)d|diagdown S|</tex> и <tex>: \exists w \in S (v, w) \subset L in E\ r(S) = T}</tex>.

Поскольку при случайном выборе графа мы приводим все ''Вершинное изопериметрическое число'' <tex>nd</tex> рёбер случайно и независимо, то для <tex>\forall</tex> ребра вероятность того, что его правый конец окажется в фиксированном множестве <tex>T</tex>, равна <tex>|T|/m</tex>. Следовательно, <tex> Prob[</tex>свойство экаспандерности графа нарушено<tex>] \leq \ \sum_{S, T}^h_{in}(\frac{|T|}{m}G)^{sd}</tex>, где суммирование происходит по всем множествам графа <tex>S \subset L \ |S| \leq k \ \forall T \subset R \ |T| = (1 - \epsilon)d|S| G</tex>. Оценим данную сумму сверху:определяется как

<tex>\sum_h_{s in}(G) = 1}^\min\limits_{k} 0 < |S|\leqslant \binomcfrac{sn}{n2}} \* cfrac{|\binomGamma_{(1 - \epsilon)sdtext{in}{m} \* (\frac{(1 - \epsilonS)sd}{m|})^{sd|S|}</tex>.,

где <tex>\sum_Gamma_{s = 1in}^{k} (\frac{ne}{s})^{s} \cdot (\frac{me}{(1 - \epsilon)sd})^{(1 - \epsilon)sd} \cdot (\frac{(1 - \epsilon)sd}{m})^{sd} \leq \sum_{s = 1}^{k} [\frac{ne}{s} \cdot (\frac{e^{(1 - \epsilon)/\epsilon} \cdot (1 - \epsilonS)sd}{m})^{\epsilon d}]^{s}</tex>.Положим — ''внутренняя граница'' <tex>m := Const * kdS</tex> (с достаточно большим значением Const), чтобы для всех возможных s выполнялось неравенство то есть множество вершин <tex>\frac{e^{(1 - \epsilon)/\epsilon} \cdot (1 - \epsilon)sd}{m} \leq 1/2S</tex>. Тогда выражение , имеющих как минимум одного соседа в квадратных скобках не превосходит <tex>ne \cdot V(1/2G) ^{\epsilon d}setminus S</tex>. Остаётся выбрать <tex>d > \frac{1}{\epsilon}\log(2en)</tex>, и мы получаем

<tex>ne \cdot Gamma_{in}(S) = \Gamma(1/2S)^\diagdown \Gamma_{\epsilon din} < 1/2(S)</tex>.==== Однородный (комбинаторный) экспандер ===={{Определение|definition=Таким образом, для выбранных значений параметров сумм не превосходят 1'''Однородный (комбинаторный) экспандер''' (англ. Это означает''combinatorial expander'') называется [[Основные определения теории графов#Ориентированные графы|граф]] <tex>G = (V, что E)</tex> с положительной вероятностью случайный двудольный граф является параметрами <tex>(n, d, \ mepsilon) \ (n = |V|</tex>, d {{---}} степень каждой вершины, константа <tex>\ kepsilon < 1)</tex>, если выполняется условие: для <tex>\ \forall S: S \subseteq V, \ d|S| \leqslant \cfrac{n}{2} \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\ Gamma(S)| > (1 + \epsilon)|S|</tex> - экспандером. Теорема доказана.

Пусть <tex>G\epsilon</tex> {{--- двудольный граф}} некоторое положительное число меньшее <tex>1</tex>.Тогда для всех достаточно больших четных <tex>Gd = d(\epsilon)</tex> имеет совершенное паросочетание тогда и только тогда, когда всех <tex>n</tex> существует однородный (комбинаторный) экспандер с параметрами <tex>(n, d, \forall S \supseteq L : |S| \leq r(Sepsilon)</tex>.

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

ПредположимЗафиксируем некоторые множества вершин <tex>S</tex> и <tex>T</tex>. Зафиксируем номер перестановки <tex>\pi_{i}</tex>. Вероятность того, что верно для каждой вершины <tex>v \in S</tex> второй конец ребра <tex>L: |L| \{v, pi_{i}(v)\}< m/tex> попадёт в <tex>T</tex>, равна

1. Поскольку мы выбираем <tex>\forall S \supseteq L (|S| \neq 0)cfrac{d}{2}</tex> строго расширяетсяперестановок независимо, то есть вероятность того, что данное событие произойдёт для всех <tex>|r(S)| > |S|i</tex>. не превосходит <tex>\measuredangle \ \ \forall x \supset V(L) : bigg(x, y) \in E</tex>. <tex>\measuredangle G^cfrac{*|T|} : L^{*n} = L \diagdown {x}</tex> и <tex>Rbigg)^{*} = R \diagdown tfrac{yd|S|}</tex>. Так как <tex>\forall S \supset L</tex> строгому неравенству теоремы, каждое подмножество <tex>L^{*2}</tex> удовлетворяет неравенству, так как только одна вершина <tex>y</tex> удалена из <tex>R</tex> следовательно по предположению индукции меньший граф <tex>G^{*}</tex> имеет паросочетание. К этому паросочетанию добавляем ребро {xТаким образом, y} что дает совершенное паросочетание.

2. Пусть Вероятность, что свойство экспандерности графа нарушено небольше <tex>\exists sum\limits_{S, T } \in L bigg(\ (cfrac{|T| }{n}\neq 0bigg)^{\tfrac{d|S|}{2}}</tex> такое, что где суммирование происходит по всем множествам вершин <tex>S</tex> размера не более <tex>\cfrac{n}{2}</tex> и по всем множествам <tex>T</tex> размера <tex>|r\lfloor(T1 + \epsilon)| = |TS|\rfloor</tex>.

По предположению индукции <tex>G_\sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}} \leqslant \sum\limits_{s = 1}</tex> имеет совершенное паросочетание ^{\tfrac{n}{2}} \dbinom{s}{n} \cdot \dbinom{(1 + \epsilon)s}{n} \cdot \bigg(\cfrac{(Заметим, что предположение индукции не может использоваться на <tex>G_1 + \epsilon)s}{n}\bigg)^{\tfrac{sd}{2}}</tex>). Пусть <tex>S \supseteq L \diagdown T(1)</tex>, тогда:

Каждый биномиальный коэффициент <tex> r_{G_{2}}(S) = r_\dbinom{Gk}(S \bigcup T) \diagdown r_{Gn}(T) \ \Rightarrow</tex> можно оценить сверху величиной <tex>|r_\bigg(\cfrac{G_ne}{2k}\bigg)^{k}| \geqslant |S \bigcup T| - |T| = |S|</tex>. Тогда

Неравенство верно, поскольку <tex>S \bigcup T</tex> удовлетворяет <tex>|r_sum\limits_{s = 1}^{\tfrac{n}{G2}} \bigg(S \bigcup Tcfrac{ne}{s}\bigg)| ^{s} \cdot \bigg(\geqslant |S cfrac{ne}{(1 + \bigcup T|</tex> и по предположению индукции <tex>|r_epsilon)s}\bigg)^{G(1 + \epsilon)s}\cdot \bigg(T\cfrac{(1 + \epsilon)s}{n}\bigg)| ^{\tfrac{sd}{2}} = |T|</tex>.

Следовательно, <tex>G_\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>G_(2)</tex> Заметим, что <tex>s \leqslant \cfrac{n}{2}</tex>, а <tex>1}+ \epsilon < 2</tex>. Таким образом, можно подобрать такое<tex>d = d(\epsilon)</tex> и , чтобы выражение в квадратных скобках в правой части <tex>G_{(2})</tex> было меньше <tex>\cfrac{1}{---2}} паросочетание для </tex> при всех значениях <tex>\epsilon</tex>. Следовательно, сумма <tex>(1)</tex> меньше единицы. Что означает, что с положительной вероятностью случайный граф является экспандером с параметрами <tex>G(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)-</tex>'''экспандером''' \ (расширяющимся графом), если <tex>n = |L| ,\ m = n, |R| = m,\ d</tex>, - степень всех вершин в левой доле <tex>L</tex> равна <tex>d</tex>), и выполняются следующие свойства расширенияесли выполняется условие:* Для любого множества для <tex>S \subset L, |S| \leqslant \dfrac{n}{1000d}</tex> множество соседей (соседи <tex>forall S</tex> лежат в <tex>R</tex>) достаточно велико: <tex>|Г(S)| > \dfrac{7}{8}d|S|</tex>.* Для любого множества <tex>S subseteq L \subset L</tex>, такого что <tex>|S| \leqslant k \ \dfrac{n}{2}</tex>, множество соседей немного больше самого множества <tex>S</tex>, а именно, <tex>|Г\Gamma(S)| > (1 - \dfrac{9}{8}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>h,  где суммирование происходит по всем множествам <tex>S \subset L \ |S| \leqslant k \ \forall T: T \subset R \ |T| = (G1 - \epsilon)d|S| </tex> графа . Оценим данную сумму сверху: <tex>G\sum\limits_{s = 1}^{k} \dbinom{s}{n} \* \dbinom{(1 - \epsilon)sd}{m} \* \bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}</tex> для . Оценивая биномиальные коэффициенты, получаем, что сумма не превосходит <tex>n\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>h(G) = \minsum\limits_{0 < |S|s = 1}^{k} \leqslant bigg[\fraccfrac{nne}{2}s} \fraccdot \bigg(\cfrac{e^{|\partial_tfrac{1 - \textepsilon}{out\epsilon}}\cdot (S1 - \epsilon)sd}{m}\bigg)|^{\epsilon d}\bigg]^{|S|s}</tex>,.

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

Таким образом, для выбранных значений параметров сумм не превосходят <tex>1</tex>. Это означает, что с положительной вероятностью случайный двудольный граф является экспандером c параметрами <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex>.}}'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>. ====Теорема о паросочетаниях ==Вершинное расширение=={{Теорема|statement=''Вершинное изопериметрическое число'' Пусть <tex>G</tex>h_{out{---}(} [[Двудольные графы|двудольный граф]].<tex>G)</tex> (также ''вершинное раширение'') графа имеет совершенное паросочетание тогда и только тогда, когда <tex>G\forall S: S \supseteq L \ |S| \leqslant \Gamma(S)</tex> определяется как.|proof=Будем доказывать по индукции

Для <tex>h_{out}(G) = \min\limits_{0 < |SL|\leqslant \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|}= 1</tex>,очевидно

где <tex>\partial_{\text{out}}(S)</tex> — ''внешняя граница'' <tex>S</tex>, то есть множество вершин из <tex>V(G)\setminus S</tex>Предположим, имеющих как минимум одного соседа в <tex>Sчто верно для </tex>. В варианте этого определения (называемом ''уникальным соседним расширением'') L: |L| <tex>\partial_{\text{out}}(S)</tex> заменяется на множество вершин из <tex>V</tex> с ''точностью одним'' соседом из <tex>Sm</tex>.

''Вершинное изопериметрическое число'' Рассмотрим два случая:# <tex>h_\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 \inL, \ |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> определяется как.}}

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

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

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

[[Алгебра|Алгебраическое ]] конструирование, основанное на графах Кэли<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 = 1 \bmod 4</tex>. В качестве группы <tex>G</tex> возьмём <tex>PGL- o(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> целочисленное решение уравнения <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>(G, S)n</tex> состоит из вершинами почти является графом Рамануджана, так как выполняется неравенство <tex>\Theta(q^3)lambda \leqslant 2\sqrt {d-1} + \epsilon</tex> вершин, и степень каждой вершины равна с вероятностью <tex>1 - o(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{n \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/ 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.]