92
правки
Изменения
м
— евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>.
Нет описания правки
(\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>.
}}
<tex>ne \cdot (1/2)^{\epsilon d} < 1/2</tex>.
Таким образом, для выбранных значений параметров сумм не превосходят 1. Это означает, что с положительной вероятностью случайный двудольный граф является экспандером c параметрами <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex>. Теорема доказана.
}}
'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>.
=== теорема о паросочетаниях ===
{{Теорема
|statement=
''Вершинное изопериметрическое число'' <tex>h_{out}(G)</tex> (также ''вершинное раширение'') графа <tex>G</tex> определяется как
<tex>h_{out}(G) = \min\limits_{0 < |S|\leqslant \frac{n}{2}} \frac{|\partial_Gamma_{\text{out}}(S)|}{|S|}</tex>,
где <tex>\partial_Gamma_{\text{out}}(S)</tex> — ''внешняя граница'' <tex>S</tex>, то есть множество вершин из <tex>V(G)\setminus S</tex>, имеющих как минимум одного соседа в <tex>S</tex>. В варианте этого определения (называемом ''уникальным соседним расширением'') <tex>\partial_Gamma_{\text{out}}(S)= </tex> заменяется на множество вершин из {<tex>v \in V</tex> с ''точностью одним'' соседом из <tex>(G) \diagdown S: \exists w \in S(v, w) \in E</tex>}.
''Вершинное изопериметрическое число'' <tex>h_{in}(G)</tex> графа <tex>G</tex> определяется как
<tex>h_{in}(G) = \min\limits_{0 < |S|\leqslant \frac{n}{2}} \frac{|\partial_Gamma_{\text{in}}(S)|}{|S|}</tex>,
где <tex>\partial_Gamma_{in}(S)</tex> — ''внутренняя граница'' <tex>S</tex>, то есть множество вершин <tex>S</tex>, имеющих как минимум одного соседа в <tex>V(G)\setminus S</tex>.
<tex>\Gamma_{in}(S) = \Gamma(S) \diagdown \Gamma_{in}(S)</tex>
===Спектральное расширение===
Если <tex>G</tex> является [[Основные определения теории графов#Часто используемые графы|d-регулярным]], возможно определение в терминах [[Линейная алгебра 1 курс|линейной алгебры ]] на основе собственных значений [[Матрица смежности графа|матрицы смежности ]] <tex>A = A(G)</tex> графа <tex>G</tex>, где <tex>A_{ij}</tex> — {{---}} число дуг между вершинами <tex>i</tex> и <tex>j</tex>. Поскольку <tex>A</tex> является симметричной, согласно спектральной теореме, <tex>A</tex> имеет <tex>n</tex> действительных собственных значений <tex>\lambda_1 lambda_{1} \ge \lambda_2 lambda_{2} \ge \cdots \ge \lambda_{n}</tex>. Известно, что эти значения лежат в промежутке <tex>[−d-d, d]</tex>.Граф регулярен тогда и только тогда, когда вектор <tex>u\in \mathbb {R} ^{n} с u_{i}=1</tex> для всех <tex>i = 1, …, \ldots n</tex> является собственным вектором матрицы <tex>A</tex>, а его собственное число будет постоянной степенью графа. Таким образом, мы имеем <tex>Au = du</tex>, и <tex>u</tex> — собственный вектор матрицы <tex>A</tex> с собственными значениями <tex>λ1 \lambda_{1} = d</tex>, где <tex>d</tex> — степень вершин графа <tex>G</tex>. Спектральный зазор графа <tex>G</tex> определяется как <tex>d−λ2d-\lambda_{2}</tex> и является мерилом спектрального расширения графа <tex>G</tex>.
Известно, что <tex>\lambda_n lambda_{n} = −d-d</tex> тогда и только тогда, когда <tex>G</tex> — {{---}} [[Двудольные графы|двудольный]]. Во многих случаях, например в лемме о перемешивании, необходимо ограничить снизу не только зазор между <tex>\lambda_1lambda_{1}</tex> и <tex>\lambda_2lambda_{2}</tex>, но и зазор между <tex>\lambda_1lambda_{1}</tex> и вторым максимальным по модулю собственным значением:
<tex>\lambda=\max\{|\lambda_2lambda_{2}|, |\lambda_{n}|\}</tex>
Поскольку это собственное значение соответствует некоторому собственному вектору, ортогональному <tex>u</tex>, его можно определить, используя отношение Рэлея:
<tex>\lambda=\max_max\limits_{0\neq v\perp u} \frac{\|Av\|_2}{\|v\|_2},</tex>gdeгде
<tex>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1/2}</tex>
{{---}} евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>. Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\tfrac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>−1-1</tex> и <tex>1</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения матрицы Кирхгофа. Для направленного графа используются сингулярные значения матрицы сопряжения A, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</tex>.
==Конструирование==
Существуют три основные стратегии создания семейств графов расширений. Первая стратегия — алгебраическая и теоретико-групповая, вторая — аналитическая, использующая аддитивную комбинаторику, и третья — комбинаторная, использующая зигзаг-произведение и связанные комбинаторные произведения.
===Маргулис-Габбер-Галил===
[[Алгебра|Алгебраическое ]] конструирование, основанное на графах Кэли, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером (Gabber) и Галилом (Galil). Для любого натурального <tex>n</tex> строим граф, <tex>G_{n}</tex> со множеством вершин <tex>\mathbb Z _{n}\times \mathbb {Z} _{n}</tex>, где <tex>\mathbb {Z} _{n}=\mathbb Z /n \mathbb Z</tex> . Для любой вершины <tex>(x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}</tex>, её восемь соседей будут
<tex>(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).</tex>
