92
правки
Изменения
м
→Однородный (комбинаторный) экспандер
{{Определение
|definition=
'''Однородный (комбинаторный) экспандер''' (англ. ''combinatorial expander'') называется [[Основные определения теории графов#Ориентированные графы|граф]] <tex>G = (V, E)</tex> с параметрами <tex>(n, d, \epsilon) \ (n = |V|</tex>, d {{---}} степень каждой вершины, константа <tex>\epsilon < 1)</tex>, если выполняется условие: для <tex>\ \forall S: S \subseteq V, \ |S| \leq \tfrac{n/}{2 } \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.
}}
'''Замечание:''' чем больше <tex>\epsilon</tex>, тем сильнее свойство расширения.
Мы выберем граф случайно и покажем, что с положительной (и даже довольно близкой к <tex>1</tex>) вероятностью такой граф оказывается экспандером. Отсюда будет следовать, что экспандеры существуют.
Оценим вероятность того, что полученный в результате граф не является экспандером, если найдется множество вершин <tex>S</tex> (состоящее из не более, чем <tex>\tfrac{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>\cfrac{|T|}{n} \cdot \cfrac{|T| - 1}{n - 1} \cdot \ldots \cdot \cfrac{|T| - |S| + 1}{n - |S| + 1} \leq \bigg(\cfrac{|T|}{n}\bigg)^{|S|}</tex>.
Поскольку мы выбираем <tex>\tfrac{d/}{2}</tex> перестановок независимо, вероятность того, что данное событие произойдёт для всех <tex>i</tex> не превосходит <tex>\bigg(\cfrac{|T|}{n}\bigg)^{(\tfrac{d/2)|S|}{2}}</tex>.
Таким образом,
Вероятность, что свойство экспандерности графа нарушено <tex>\leq \sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{(\tfrac{d/2)|S|}{2}}</tex>,где суммирование происходит по всем множествам вершин <tex>S</tex> размера не более <tex>\tfrac{n/}{2}</tex> и по всем множествам <tex>T</tex> размера <tex>\lfloor(1 + \epsilon)|S|\rfloor</tex>.
Оценим сумму:
<tex>\sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{(\tfrac{d/2)|S|}{2}} \leq \sum\limits_{s = 1}^{\tfrac{n/}{2}} \dbinom{s}{n} \cdot \dbinom{(1 + \epsilon)s}{n} \cdot \bigg(\cfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd/}{2}}</tex>. <tex>(1)</tex>
Каждый биномиальный коэффициент <tex>\dbinom{k}{n}</tex> можно оценить сверху величиной <tex>(\cfrac{ne}{k})^{k}</tex>. Тогда
<tex>
\sum\limits_{s = 1}^{\tfrac{n/}{2}}
\bigg(\cfrac{ne}{s}\bigg)^{s} \cdot
\bigg(\cfrac{ne}{(1 + \epsilon)s}\bigg)^{(1 + \epsilon)s} \cdot
\bigg(\cfrac{(1 + \epsilon)s}{n}\bigg)^{\tfrac{sd/}{2}} =</tex>
<tex>\sum\limits_{s = 1}^{\tfrac{n/}{2}} \bigg[(\tfrac{s / }{n})^{\tfrac{d/}{2 } - 2 - \epsilon} \cdot (1 + \epsilon)^{\tfrac{d/}{2}} \cdot \cfrac{e^{1 + \epsilon} }{(1 + \epsilon)^{1 + \epsilon} }\bigg]^s</tex>. <tex>(2)</tex>
Заметим, что <tex>s \leq \tfrac{n/}{2}</tex>, а <tex>1 + \epsilon < 2</tex>. Таким образом, можно подобрать такое<tex>d = d(\epsilon)</tex>, чтобы выражение в квадратных скобках в правой части <tex>(2)</tex> было меньше <tex>\tfrac{1/}{2}</tex> при всех значениях <tex>\epsilon</tex>. Следовательно, сумма <tex>(1)</tex> меньше единицы. Что означает, что с положительной вероятностью случайный граф является экспандером с параметрами <tex>(n, d, \epsilon)</tex>.
}}
