92
правки
Изменения
м
Нет описания правки
Оценим вероятность того, что полученный в результате граф не является экспандером, если найдется множество вершин <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>\leq \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}} \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(\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 \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>.
}}
{{Определение
|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| \leq leqslant k \ \ |\Gamma(S)| > (1 - \epsilon)d|S|</tex>.
}}
'''Замечание 1:''' чем меньше значение <tex>\epsilon</tex> в данном определении, тем сильнее свойство расширения.
{{Теорема
|statement=
Пусть <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>.
|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> \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>. Оценим данную сумму сверху:
<tex>\sum\limits_{s = 1}^{k} \dbinom{s}{n} \* \dbinom{(1 - \epsilon)sd}{m} \* \bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}</tex>.
\bigg(\cfrac{me}{(1 - \epsilon)sd}\bigg)^{(1 - \epsilon)sd} \cdot
\bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}
\leq leqslant </tex>
<tex>\sum\limits_{s = 1}^{k}
</tex>.
Положим <tex>m = Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных s выполнялось неравенство <tex>\cfrac{e^{(1 - \epsilon)/\epsilon} \cdot (1 - \epsilon)sd}{m} \leq 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>(n, \ m, \ k, \ d, \ \epsilon)</tex>.
'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>.
==== теорема Теорема о Паросочетаниях паросочетаниях ====
{{Теорема
|statement=
Пусть <tex>G</tex> {{---}} [[Двудольные графы|двудольный граф]].
<tex>G</tex> имеет совершенное паросочетание тогда и только тогда, когда <tex>\forall S: S \supseteq L \ |S| \leq leqslant \Gamma(S)</tex>.
|proof=
Будем доказывать по индукции
где <tex>\|v\|_2=\left(\sum\limits_{i=1}^{n} v_i^2\right)^{\tfrac{1}{2}}</tex> {{---}} евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>.
Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\cfrac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>(-1</tex> и <tex>, 1)</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения [[Матрица Кирхгофа|матрицы Кирхгофа]]. Для направленного графа используются сингулярные значения матрицы сопряжения <tex>A</tex>, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</tex>.
==Конструирование==
<tex>\forall n</tex> граф <tex>G_{n}</tex> второе по величине собственное число удовлетворяет неравенству
<tex>\lambda(G)\leq leqslant 5 \sqrt{2}</tex>.
}}
{{Теорема
|statement=
[[Основные определения теории графов#Часто используемые графы|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>.
==Примеры применения экспандеров==
Первоначально интерес к экспандерам возник с целью построения устойчивой сети (телефонов или компьютеров) — число дуг графов расширения с ограниченным значением регулярности растет линейно по отношению к числу вершин.
Экспандеры нашли широкое применение в теории вычислительных машин и систем, для построения алгоритмов, в корректирующих кодах<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>\left|E(S,T)-{\cfrac {d\cdot |S|\cdot |T|}{n}}\right|\leq leqslant d\lambda {\sqrt {|S|\cdot |T|}}</tex>,
где <tex>\lambda </tex> — абсолютное значение нормализованного второго по величине собственного значения.
