92
правки
Изменения
м
→Двудольный экспандер
'''Замечание 1:''' чем меньше значение <tex>\epsilon</tex> в данном определении, тем сильнее свойство расширения.
'''Замечание 2:''' в приложениях как правило используют двудольные экспандеры с <tex>\epsilon < \tfrac{1/}{2}</tex>, а для применения в теории кодирования (для построения экспандерных кодов) часто требуются двудольные экспандеры с ещё меньшими значениями <tex>\epsilon</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>\tfrac{|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>. Оценим данную сумму сверху:
</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 (\tfrac{1/}{2) } ^{\epsilon d}</tex>. Остаётся выбрать <tex>d > \cfrac{1}{\epsilon}\log(2en)</tex>, и мы получаем <tex>ne \cdot (\tfrac{1/}{2)}^{\epsilon d} < \tfrac{1/}{2}</tex>.
Таким образом, для выбранных значений параметров сумм не превосходят <tex>1</tex>. Это означает, что с положительной вероятностью случайный двудольный граф является экспандером c параметрами <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex>.
