92
правки
Изменения
м
→Двудольный экспандер
Граф не является экспандером, если <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>\tfraccfrac{|T|}{m}</tex>. Следовательно, вероятность, что свойство экспандерности графа нарушено <tex> \leq \ \sum\limits_{S, T}\bigg(\cfrac{|T|}{m}\bigg)^{sd}</tex>,
где суммирование происходит по всем множествам <tex>S \subset L \ |S| \leq k \ \forall T: T \subset R \ |T| = (1 - \epsilon)d|S| </tex>. Оценим данную сумму сверху:
\bigg(\cfrac{ne}{s}\bigg)^{s} \cdot
\bigg(\cfrac{me}{(1 - \epsilon)sd}\bigg)^{(1 - \epsilon)sd} \cdot
\bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}
\leq </tex>
</tex>.
Положим <tex>m = Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных s выполнялось неравенство <tex>\cfrac{e^{(1 - \epsilon)/\epsilon} \cdot (1 - \epsilon)sd}{m} \leq \cfrac{1}{2}</tex>. Тогда выражение в квадратных скобках не превосходит <tex>ne \cdot \tfraccfrac{1ne}{2} ^{\epsilon d}}</tex>. Остаётся выбрать <tex>d > \cfrac{1}{\epsilon}\log(2en)</tex>, и мы получаем <tex>ne \cdot \tfraccfrac{1ne}{2}^{\epsilon d}} < \tfraccfrac{1}{2}</tex>.
Таким образом, для выбранных значений параметров сумм не превосходят <tex>1</tex>. Это означает, что с положительной вероятностью случайный двудольный граф является экспандером c параметрами <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex>.
