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 leqslant \cfrac{n}{2} \ \ \exists \ \Gamma(S)</tex>, которое достаточно велико, то есть <tex>|\Gamma(S)| > (1 + \epsilon)|S|</tex>.
}}
'''Замечание:''' чем больше <tex>\epsilon</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 leqslant \bigg(\cfrac{|T|}{n}\bigg)^{|S|}</tex>.
Поскольку мы выбираем <tex>\cfrac{d}{2}</tex> перестановок независимо, вероятность того, что данное событие произойдёт для всех <tex>i</tex> не превосходит <tex>\bigg(\cfrac{|T|}{n}\bigg)^{\tfrac{d|S|}{2}}</tex>.
