92
правки
Изменения
м
→Двудольный экспандер
Поскольку при случайном выборе графа мы приводим все <tex>nd</tex> рёбер случайно и независимо, то для <tex>\forall</tex> ребра вероятность того, что его правый конец окажется в фиксированном множестве <tex>T</tex>, равна <tex>|T|/m</tex>. Следовательно,
<tex>Prob[</tex>свойство экспандерности графа нарушено<tex>] \leq \ \sum_{S, T}^{}(\fraccfrac{|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} \binomdbinom{s}{n} \* \binomdbinom{(1 - \epsilon)sd}{m} \* (\fraccfrac{(1 - \epsilon)sd}{m})^{sd}</tex>.
Оценивая биномиальные коэффициенты, получаем, что сумма не превосходит
<tex>
\sum_{s = 1}^{k}
(\fraccfrac{ne}{s})^{s} \cdot (\fraccfrac{me}{(1 - \epsilon)sd})^{(1 - \epsilon)sd} \cdot (\fraccfrac{(1 - \epsilon)sd}{m})^{sd} \leq </tex> <tex>\sum_{s = 1}^{k} \big[\fraccfrac{ne}{s} \cdot (\fraccfrac{e^{(1 - \epsilon)/\epsilon} \cdot (1 - \epsilon)sd}{m})^{\epsilon d}\big]^{s}
</tex>.
Положим <tex>m = Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных s выполнялось неравенство <tex>\fraccfrac{e^{(1 - \epsilon)/\epsilon} \cdot (1 - \epsilon)sd}{m} \leq 1/2</tex>. Тогда выражение в квадратных скобках не превосходит <tex>ne \cdot (1/2) ^{\epsilon d}</tex>. Остаётся выбрать <tex>d > \fraccfrac{1}{\epsilon}\log(2en)</tex>, и мы получаем
<tex>ne \cdot (1/2)^{\epsilon d} < 1/2</tex>.
}}
'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>.
=== теорема о паросочетаниях ===
{{Теорема
