92
правки
Изменения
м
→Двудольный экспандер
<tex>\sum\limits_{s = 1}^{k}
\bigg[\cfrac{ne}{s} \cdot
\bigg(\cfrac{e^{(\tfrac{1 - \epsilon)/}{\epsilon}} \cdot
(1 - \epsilon)sd}{m}\bigg)^{\epsilon d}\bigg]^{s}
</tex>.
Положим <tex>m = Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных s выполнялось неравенство <tex>\cfrac{e^{(\tfrac{1 - \epsilon)/}{\epsilon}} \cdot (1 - \epsilon)sd}{m} \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>.
