92
правки
Изменения
м
→Однородный (комбинаторный) экспандер
Зафиксируем некоторые множества вершин <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>\fraccfrac{|T|}{n} \cdot \fraccfrac{|T| - 1}{n - 1} \cdot \ldots \cdot \fraccfrac{|T| - |S| + 1}{n - |S| + 1} \leq (\fraccfrac{|T|}{n})^{|S|}</tex>.
Поскольку мы выбираем <tex>d/2</tex> перестановок независимо, вероятность того, что данное событие произойдёт для всех <tex>i</tex> не превосходит <tex>(\fraccfrac{|T|}{n})^{(d/2)|S|}</tex>.
Таким образом,
Prob[свойство экспандерности графа нарушено] <tex>\leq \sum_{S, T} (\fraccfrac{|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}(\fraccfrac{|T|}{n})^{(d/2)|S|} \leq \sum_{s = 1}^{n/2}\binomdbinom{s}{n} \cdot \binomdbinom{(1 + \epsilon)s}{n} \cdot (\fraccfrac{(1 + \epsilon)s}{n})^{sd/2}</tex>. (1)
Каждый биномиальный коэффициент <tex>\binomdbinom{k}{n}</tex> можно оценить сверху величиной <tex>(\fraccfrac{ne}{k})^{k}</tex>. Тогда
<tex>
\sum_{s = 1}^{n/2}
(\fraccfrac{ne}{s})^{s} \cdot (\fraccfrac{ne}{(1 + \epsilon)s})^{(1 + \epsilon)s} \cdot (\fraccfrac{(1 + \epsilon)s}{n})^{sd/2} = \sum_{s = 1}^{n/2} \big[(s / n)^{d/2 - 2 - \epsilon} \cdot (1 + \epsilon)^{d/2} \cdot \fraccfrac{e^{1 + \epsilon} }{(1 + \epsilon)^{1 + \epsilon} }\big]^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>.
}}
=== Двудольный экспандер ===
{{Определение
