Изменения

'''Граф-экспандер ''' (или расширяющийся граф, англ. ''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 \subseteq V, \ |S| \leq leqslant \tfraccfrac{n}{2} \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.

Оценим вероятность того, что полученный в результате граф не является экспандером, если найдется множество вершин <tex>S</tex> (состоящее из не более, чем <tex>\tfraccfrac{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} \leq leqslant \bigg(\cfrac{|T|}{n}\bigg)^{|S|}</tex>.

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

Вероятность, что свойство экспандерности графа нарушено небольше <tex>\leq \sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}}</tex>,где суммирование происходит по всем множествам вершин <tex>S</tex> размера не более <tex>\tfraccfrac{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}} \leq 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[\bigg(\tfraccfrac{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 \leq leqslant \tfraccfrac{n}{2}</tex>, а <tex>1 + \epsilon < 2</tex>. Таким образом, можно подобрать такое<tex>d = d(\epsilon)</tex>, чтобы выражение в квадратных скобках в правой части <tex>(2)</tex> было меньше <tex>\tfraccfrac{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> \leq leqslant \ \sum\limits_{S, T}\bigg(\cfrac{|T|}{m}\bigg)^{sd}</tex>,

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

\bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd} \leq leqslant </tex>

\bigg(\cfrac{e^{(\tfrac{1 - \epsilon)/}{\epsilon}} \cdot

Положим <tex>m = Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных s выполнялось неравенство <tex>\cfrac{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 > \cfrac{1}{\epsilon}\log(2en)</tex>, и мы получаем  <tex>\cfrac{ne \cdot (1/}{2)^{\epsilon d}} < \cfrac{1/}{2}</tex>.

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

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

 1. # <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) что дает совершенное паросочетание. 2. # Пусть <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>.

где минимум берётся по всем непустым множествам <tex>S</tex> не более чем <tex>\cfrac{n/}{2}</tex> вершин и <tex>\partial(S)</tex> — ''граничные дуги'' множества <tex>S</tex>, то есть, множество дуг с единственной вершиной в <tex>S</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>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1/2}</tex> {{---}} евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>. Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\frac cfrac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>(-1</tex> и <tex>, 1)</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения [[Матрица Кирхгофа|матрицы Кирхгофа]]. Для направленного графа используются сингулярные значения матрицы сопряжения <tex>A</tex>, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</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>n</tex> строим граф, <tex>G_{n}</tex> со множеством  В качестве множества вершин графа возьмём <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>\lambda(G)\leq leqslant 5 \sqrt{2}</tex>.

[[Основные определения теории графов#Часто используемые графы|d-регулярный граф]] называется графом Рамануджана, если его второе по модулю собственное число <tex> \lambda \leq leqslant 2\sqrt {d-1} - o(1)</tex>.

'''Замечание:''' случайный [[Основные определения теории графов#Часто используемые графы|d-регулярный граф]] с <tex>n</tex> вершинами почти является графом Рамануджана, так как выполняется неравенство <tex> \lambda \leq 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>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 \cfrac{77nd}{8\cdot 1000d}d= \cfrac{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''<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<ref>Irit Dinur The PCP theorem by gap amplification // Journal of the ACM. — 2007. — Т. 54, вып. 3. — С. 12. — DOI:10.1145/1236457.1236459</ref>]]. В криптографии экспандеры используются для создания [[Универсальное семейство хеш-функций|хеш-функций]].

Лемма о перемешивании утверждает, что для любых двух подмножеств вершин <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)-{\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>.