92
правки
Изменения
м
Prob[Вероятность, что свойство экспандерности графа нарушено] <tex>\leq \sum_sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{(d/2)|S|}</tex>,
→Однородный (комбинаторный) экспандер
{{Теорема
|statement=
Пусть <tex>\epsilon</tex> {{---}} некоторое положительное число меньшее <tex>1</tex>. Тогда для всех достаточно больших четных <tex>d = d(\epsilon)</tex> и всех <tex>n</tex> существует однородный (комбинаторный) экспандер с параметрами <tex>(n, d, \epsilon)</tex>.
|proof=
Мы выберем граф случайно и покажем, что с положительной (и даже довольно близкой к <tex>1</tex>) вероятностью такой граф оказывается экспандером. Отсюда будет следовать, что экспандеры существуют.
Оценим вероятность того, что полученный в результате граф не является экспандером, если найдется множество вершин <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>\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>d/2</tex> перестановок независимо, вероятность того, что данное событие произойдёт для всех <tex>i</tex> не превосходит <tex>\bigg(\cfrac{|T|}{n}\bigg)^{(d/2)|S|}</tex>.
Таким образом,
где суммирование происходит по всем множествам вершин <tex>S</tex> размера не более <tex>n/2</tex> и по всем множествам <tex>T</tex> размера <tex>\lfloor(1 + \epsilon)|S|\rfloor</tex>.
Оценим сумму:
<tex>\sum_sum\limits_{S, T}\bigg(\cfrac{|T|}{n}\bigg)^{(d/2)|S|} \leq \sum_sum\limits_{s = 1}^{n/2} \dbinom{s}{n} \cdot \dbinom{(1 + \epsilon)s}{n} \cdot (\cfrac{(1 + \epsilon)s}{n})^{sd/2}</tex>. (1)
Каждый биномиальный коэффициент <tex>\dbinom{k}{n}</tex> можно оценить сверху величиной <tex>(\cfrac{ne}{k})^{k}</tex>. Тогда
<tex>
\sum_sum\limits_{s = 1}^{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)^{sd/2} =</tex>
<tex>\sum_sum\limits_{s = 1}^{n/2} \bigbigg[(s / n)^{d/2 - 2 - \epsilon} \cdot (1 + \epsilon)^{d/2} \cdot \cfrac{e^{1 + \epsilon} }{(1 + \epsilon)^{1 + \epsilon} }\bigbigg]^s</tex>. (2)
Заметим, что <tex>s \leq n/2</tex>, а <tex>1 + \epsilon < 2</tex>. Таким образом, можно подобрать такое
