92
правки
Изменения
м
Нет описания правки
{{Теорема
|statement=
Пусть <tex>\forall nepsilon</tex>, <tex>\forall \epsilon < {{---}} некоторое положительное число меньшее 1</tex>. Тогда для всех достаточно больших четных <tex>d = d(\epsilon)</tex> и всех <tex>n</tex> существует однородный(комбинаторный) экспандер с параметрами <tex>(n, d, \epsilon)</tex>.
|proof=
Мы выберем граф случайно и покажем, что с положительной (и даже довольно близкой к 1) вероятностью такой граф оказывается экспандером. Отсюда будет следовать, что экспандеры существуют.
{{Определение
|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 \ \ |\Gamma(S)| > (1 - \epsilon)d|S|</tex>.
}}
'''Замечание 1:''' чем меньше значение <tex>\epsilon</tex> в данном определении, тем сильнее свойство расширения.
Выберем случайный граф, то есть для <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>|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>.
(1 - \epsilon)sd}{m})^{\epsilon d}]^{s}
</tex>.
Положим <tex>m := Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных 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>.
