92
правки
Изменения
определение двудольного экспандера
для достаточно больших четных <tex>d = d(\epsilon)</tex> существует однородный(комбинаторный) экспандер с параметрами <tex>(n, d, \epsilon)</tex>.
}}
{{Определение
|definition=
'''Двудольный экспандер''' называется граф <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 \subseteq L \ |S| \leq k \ \ |r(S)| > (1 - \epsilon)d|S|</tex>.
}}
'''Замечание 1:''' чем меньше значение <tex>\epsilon</tex> в данном определении, тем сильнее свойство расширения.
'''Замечание 2:''' в приложениях как правило используют двудольные экспандеры с <tex>\epsilon < 1/2</tex>, а для применения в теории кодирования (для построения экспандерных кодов) часто требуются двудольные экспандеры с ещё меньшими значениями <tex>\epsilon</tex>.
{{Теорема
|statement=
Пусть <tex>\epsilon</tex> - некоторое положительное число. Тогда для <tex>\forall \ n</tex> и <tex>k \leq n</tex> найдется <tex>d = O(\log n)</tex> и <tex>m = O(dk)</tex> такие, что <tex>\exists</tex> двудольный экспандер с параметрами <tex>(n, m, d, k, \epsilon)</tex>.
'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\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 \ 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}^{}(\frac{|T|}{m})^{sd}</tex>, где суммирование происходит по всем множествам <tex>S \subset L \ |S| \leq k \ \forall T \subset R \ |T| = (1 - \epsilon)d|S| </tex>. Оценим данную сумму сверху:
<tex>\sum_{s = 1}^{k} \binom{s}{n} \* \binom{(1 - \epsilon)sd}{m} \* (\frac{(1 - \epsilon)sd}{m})^{sd}</tex>.
Оценивая биномиальные коэффициенты, получаем, что сумма не превосходит
<tex>
\sum_{s = 1}^{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 - \epsilon)sd}{m})^{\epsilon d}]^{s}
</tex>.
Положим <tex>m := Const * kd</tex> (с достаточно большим значением Const), чтобы для всех возможных s выполнялось неравенство <tex>\frac{e^{(1 - \epsilon)/\epsilon} \cdot (1 - \epsilon)sd}{m} \leq 1/2</tex>. Тогда выражение в квадратных скобках не превосходит <tex>ne \cdot (1/2) ^{\epsilon d}</tex>. Остаётся выбрать <tex>d > \frac{1}{\epsilon}\log(2en)</tex>, и мы получаем
<tex>ne \cdot (1/2)^{\epsilon d} < 1/2</tex>.
Таким образом, для выбранных значений параметров сумм не превосходят 1. Это означает, что с положительной вероятностью случайный двудольный граф является <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex> - экспандером. Теорема доказана.
}}
{{Определение
|definition=
