92
правки
Изменения
доказательство существования однородного экспандера
'''Замечание:''' Несвязный граф не является экспандером. Любой связный граф является экспандером, однако различные связные графы имеют различные параметры расширителя. Полный граф имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.
== Основные определения ==
{{Определение
|definition=
Множество соседей для множества вершин <tex>S</tex> называется <tex>\Gamma(S) = \{v: \exists w \in S:\ (v, w) \in E\}</tex>.
}}
'''Замечание:''' в графе могут присутствовать кратные ребра и петли. Если у каждой вершины есть петли, то <tex>\forall S \supseteq \Gamma(S)</tex>.
=== Однородный (комбинаторный) экспандер ===
{{Определение
|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 \</tex> множество соседей <tex>rGamma(S) = \{v: \exists w \in S,\ (v, w) \in E\}</tex>, которое достаточно велико, то есть <tex>|r\Gamma(S)| > (1 + \epsilon)|S|</tex>.
}}
'''Замечание 1:''' в графе могут присутствовать кратные ребра и петли. Если у каждой вершины есть петли, то <tex>\forall S \supseteq r(S)</tex>. '''Замечание 2:''' чем больше <tex>\epsilon</tex>, тем сильнее свойство расширения.
{{Теорема
|statement=
<tex>\forall n</tex>, <tex>\forall \epsilon < 1</tex>
для достаточно больших четных <tex>d = d(\epsilon)</tex> существует однородный(комбинаторный) экспандер с параметрами <tex>(n, d, \epsilon)</tex>.
|proof=
Мы выберем граф случайно и покажем, что с положительной (и даже довольно близкой к 1) вероятностью такой граф оказывается экспандером. Отсюда будет следовать, что экспандеры существуют.
Оценим вероятность того, что полученный в результате граф не является экспандером, если найдется множество вершин <tex>S</tex> (состоящее из не более, чем <tex>n/2</tex> вершин), все соседи которого лежат в некотором множестве <tex>T</tex>, состоящем из <tex>\lfloor (1 + \epsilon)|S|\rfloor</tex> вершин.
Зафиксируем некоторые множества вершин <tex>S</tex> и <tex>T</tex>. Зафиксируем номер перестановки <tex>\pi_{i}</tex>. Вероятность того, что для каждой вершины <tex>v \in S</tex> второй конец ребра {<tex>v, pi_{i}(v)</tex>} попадёт в <tex>T</tex>, равна
<tex>\frac{|T|}{n} \cdot \frac{|T| - 1}{n - 1} \cdot \ldots \cdot \frac{|T| - |S| + 1}{n - |S| + 1} \leq (\frac{|T|}{n})^{|S|}</tex>.
Поскольку мы выбираем <tex>d/2</tex> перестановок независимо, вероятность того, что данное событие произойдёт для всех <tex>i</tex> не превосходит <tex>(\frac{|T|}{n})^{(d/2)|S|}</tex>.
Таким образом,
Prob[свойство экспандерности графа нарушено] <tex>\leq \sum_{S, T} (\frac{|T|}{n})^{(d/2)|S|}</tex>,
где суммирование происходит по всем множествам вершин <tex>S</tex> размера не более <tex>n/2</tex> и по всем множествам <tex>T</tex> размера <tex>\lfloor(1 + \epsilon)|S|\rfloor</tex>.
Оценим сумму:
<tex>\sum_{S, T}(\frac{|T|}{n})^{(d/2)|S|} \leq \sum_{s = 1}{n/2}\binom{s}{n} \cdot \binom{(1 + \epsilon)s}{n} \cdot (\frac{(1 + \epsilon)s}{n})^{sd/2}</tex>. (1)
Каждый биномиальный коэффициент <tex>\binom{k}{n}</tex> можно оценить сверху величиной <tex>(\frac{ne}{k})^{k}</tex>. Тогда
<tex>
\sum_{s = 1}^{n/2}
(\frac{ne}{s})^{s} \cdot
(\frac{ne}{(1 + \epsilon)s})^{(1 + \epsilon)s} \cdot
(\frac{(1 + \epsilon)s}{n})^{sd/2} = \sum_{s = 1}^{n/2} [(s / n)^{d/2 - 2 - \epsilon} \cdot (1 + \epsilon)^{d/2} \cdot \frac{e^{1 + \epsilon} }{(1 + \epsilon)^{1 + \epsilon} }]^s</tex>. (2)
Заметим, что <tex>s leq n/2</tex>, а <tex>1 + \epsilon < 2</tex>. Таким образом, можно подобрать такое
<tex>d = d(\epsilon)</tex>, чтобы выражение в квадратных скобках в правой части (2) было меньше <tex>1/2</tex> при всех значениях <tex>\epsilon</tex>. Следовательно, сумма (1) меньше единицы. Что означает, что с положительной вероятностью случайный граф является экспандером с параметрами <tex>(n, d, \epsilon)</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 \ \ |r\Gamma(S)| > (1 - \epsilon)d|S|</tex>.
}}
'''Замечание 1:''' чем меньше значение <tex>\epsilon</tex> в данном определении, тем сильнее свойство расширения.
Выберем случайный граф, то есть для <tex>\forall \ v \in L</tex> случайно и независимо выбираем <tex>d</tex> соседей в <tex>R</tex> (разрешаются кратные ребра). Покажем с большой вероятностью такой граф оказывается экспандером.
Граф не является экспандером, если <tex>\exists T \subset R \ |T| = (1 - \epsilon)d|S|</tex> и <tex>\exists S \subset L \ r\Gamma(S) = T</tex>.
Поскольку при случайном выборе графа мы приводим все <tex>nd</tex> рёбер случайно и независимо, то для <tex>\forall</tex> ребра вероятность того, что его правый конец окажется в фиксированном множестве <tex>T</tex>, равна <tex>|T|/m</tex>. Следовательно, <tex> Prob[</tex>свойство экаспандерности экспандерности графа нарушено<tex>] \leq \ \sum_{S, T}^{}(\frac{|T|}{m})^{sd}</tex>, где суммирование происходит по всем множествам <tex>S \subset L \ |S| \leq k \ \forall T \subset R \ |T| = (1 - \epsilon)d|S| </tex>. Оценим данную сумму сверху:
<tex>\sum_{s = 1}^{k} \binom{s}{n} \* \binom{(1 - \epsilon)sd}{m} \* (\frac{(1 - \epsilon)sd}{m})^{sd}</tex>.
|statement=
Пусть <tex>G</tex> - двудольный граф.
<tex>G</tex> имеет совершенное паросочетание тогда и только тогда, когда <tex>\forall S \supseteq L |S| \leq r\Gamma(S)</tex>.
|proof=
Будем доказывать по индукции
Рассмотрим два случая:
1. <tex>\forall S \supseteq L, |S| \neq 0</tex> строго расширяется, то есть <tex>|r\Gamma(S)| > |S|</tex>.
Выберем <tex>\forall x \supset V(L) : (x, y) \in E</tex>. Тогда рассмотрим двудольный граф <tex>G^{*}</tex>, у которого левая доля <tex>L^{*} = L \diagdown {x}</tex>, а правая <tex>R^{*} = R \diagdown {y}</tex>. Так как <tex>\forall S \supset L</tex> удовлетворяет строгому неравенству теоремы, то каждое подмножество <tex>L^{*}</tex> удовлетворяет неравенству, поскольку только одна вершина <tex>y</tex> была удалена из <tex>R</tex>. Следовательно, по предположению индукции меньший граф <tex>G^{*}</tex> имеет паросочетание. К этому паросочетанию добавляем ребро (x, y) что дает совершенное паросочетание.
2. Пусть <tex>\exists\ T \in L, \ |T| \neq 0</tex> такое, что <tex>|r\Gamma(T)| = |T|</tex>.
<tex>\measuredangle</tex> порожденные графы <tex>G_{1} = T \cup r\Gamma(T)</tex> и <tex>G_{2} = L \diagdown T \cup R \diagdown r\Gamma(T)</tex>.
По предположению индукции <tex>G_{1}</tex> имеет совершенное паросочетание (Заметим, что предположение индукции не может использовано непосредственно на <tex>G_{2}</tex>).
