Изменения

Перейти к: навигация, поиск

Графы-экспандеры

101 байт добавлено, 00:36, 21 декабря 2017
м
Двудольный экспандер
Граф не является экспандером, если <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_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>. Оценим данную сумму сверху:
<tex>\sum_sum\limits_{s = 1}^{k} \dbinom{s}{n} \* \dbinom{(1 - \epsilon)sd}{m} \* \bigg(\cfrac{(1 - \epsilon)sd}{m}\bigg)^{sd}</tex>.
Оценивая биномиальные коэффициенты, получаем, что сумма не превосходит
<tex>
\sum_sum\limits_{s = 1}^{k} \bigg(\cfrac{ne}{s}\bigg)^{s} \cdot \bigg(\cfrac{me}{(1 - \epsilon)sd}\bigg)^{(1 - \epsilon)sd} \cdot
(\cfrac{(1 - \epsilon)sd}{m})^{sd}
\leq </tex>
<tex>\sum_sum\limits_{s = 1}^{k} \bigbigg[\cfrac{ne}{s} \cdot \bigg(\cfrac{e^{(1 - \epsilon)/\epsilon} \cdot (1 - \epsilon)sd}{m}\bigg)^{\epsilon d}\bigbigg]^{s}
</tex>.
<tex>ne \cdot (1/2)^{\epsilon d} < 1/2</tex>.
Таким образом, для выбранных значений параметров сумм не превосходят <tex>1</tex>. Это означает, что с положительной вероятностью случайный двудольный граф является экспандером c параметрами <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex>.
}}
'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>.
92
правки

Навигация