92
правки
Изменения
м
Нет описания правки
{{Определение
|definition=
'''Однородный (комбинаторный) экспандер''' называется [[Основные определения теории графов#Ориентированные графы|граф]] <tex>G = (V, E)</tex> с параметрами <tex>(n, d, \epsilon) \ (n = |V|</tex>, d {{- --}} степень каждой вершины, константа <tex>\epsilon < 1)</tex>, если выполняется условие:
для <tex>\ \forall S \subseteq V, \ |S| \leq n/2 \ \ \exists \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.
}}
{{Определение
|definition=
'''Двудольный экспандер''' называется [[Двудольные графы|двудольный граф]] <tex>G = (L,\ R,\ E)\ (L</tex> и <tex>R</tex> {{- --}} вершины левой и правой доли соответственно, <tex>E</tex> {{--- }} ребра графа <tex>G</tex>) с параметрами <tex>(n,\ m,\ d,\ e)\ (n = |L|,\ m = |R|,\ d</tex> - степень всех вершин в левой доле), если выполняется условие: для <tex>\forall S \subseteq L \ |S| \leq k \ \ |\Gamma(S)| > (1 - \epsilon)d|S|</tex>.
}}
'''Замечание 1:''' чем меньше значение <tex>\epsilon</tex> в данном определении, тем сильнее свойство расширения.
{{Теорема
|statement=
Пусть <tex>\epsilon</tex> {{- --}} некоторое положительное число. Тогда для <tex>\forall \ n</tex> и <tex>k \leq n</tex> найдется <tex>d = O(\log n)</tex> и <tex>m = O(dk)</tex> такие, что <tex>\exists</tex> двудольный экспандер с параметрами <tex>(n, m, d, k, \epsilon)</tex>.
|proof=
Выберем случайный граф, то есть для <tex>\forall \ v \in L</tex> случайно и независимо выбираем <tex>d</tex> соседей в <tex>R</tex> (разрешаются кратные ребра). Покажем с большой вероятностью такой граф оказывается экспандером.
</tex>.
Положим <tex>m := Const * kd</tex> (с достаточно большим значением <tex>Const</tex>), чтобы для всех возможных s выполнялось неравенство <tex>\frac{e^{(1 - \epsilon)/\epsilon} \cdot (1 - \epsilon)sd}{m} \leq 1/2</tex>. Тогда выражение в квадратных скобках не превосходит <tex>ne \cdot (1/2) ^{\epsilon d}</tex>. Остаётся выбрать <tex>d > \frac{1}{\epsilon}\log(2en)</tex>, и мы получаем
<tex>ne \cdot (1/2)^{\epsilon d} < 1/2</tex>.
Таким образом, для выбранных значений параметров сумм не превосходят 1. Это означает, что с положительной вероятностью случайный двудольный граф является экспандером c параметрами <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex> - экспандером. Теорема доказана.
}}
'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>.
{{Теорема
|statement=
Пусть <tex>G</tex> {{- --}} [[Двудольные графы|двудольный граф]].
<tex>G</tex> имеет совершенное паросочетание тогда и только тогда, когда <tex>\forall S \supseteq L |S| \leq \Gamma(S)</tex>.
|proof=
