92
правки
Изменения
м
Нет описания правки
Оценим сумму:
<tex>\sum\limits_{S, T} \bigg(\cfrac{|T|}{n}\bigg)^{(d/2)|S|} \leq \sum\limits_{s = 1}^{n/2} \dbinom{s}{n} \cdot \dbinom{(1 + \epsilon)s}{n} \cdot (\cfrac{(1 + \epsilon)s}{n})^{sd/2}</tex>. <tex>(1)</tex>
Каждый биномиальный коэффициент <tex>\dbinom{k}{n}</tex> можно оценить сверху величиной <tex>(\cfrac{ne}{k})^{k}</tex>. Тогда
\bigg(\cfrac{(1 + \epsilon)s}{n}\bigg)^{sd/2} =</tex>
<tex>\sum\limits_{s = 1}^{n/2} \bigg[(s / n)^{d/2 - 2 - \epsilon} \cdot (1 + \epsilon)^{d/2} \cdot \cfrac{e^{1 + \epsilon} }{(1 + \epsilon)^{1 + \epsilon} }\bigg]^s</tex>. <tex>(2)</tex>
Заметим, что <tex>s \leq n/2</tex>, а <tex>1 + \epsilon < 2</tex>. Таким образом, можно подобрать такое
<tex>d = d(\epsilon)</tex>, чтобы выражение в квадратных скобках в правой части <tex>(2) </tex> было меньше <tex>1/2</tex> при всех значениях <tex>\epsilon</tex>. Следовательно, сумма <tex>(1) </tex> меньше единицы. Что означает, что с положительной вероятностью случайный граф является экспандером с параметрами <tex>(n, d, \epsilon)</tex>.
}}
== Определения расширений ==
===Реберное расширение===
''Рёберное расширение'' (также ''изопериметрическое число'' или константа Чигера<ref>[https[wikipedia://en.wikipedia.org/wiki/Cheeger_constant|Wikipedia {{---}} константа Чигера]]</ref>) <tex>h(G)</tex> графа <tex>G</tex> для <tex>n</tex> вершин определяется как
<tex>h(G) = \min\limits_{0 < |S|\leqslant \cfrac{n}{2}} \cfrac{|\partial_{\text{out}}(S)|}{|S|}</tex>,
===Спектральное расширение===
Если <tex>G</tex> является [[Основные определения теории графов#Часто используемые графы|d-регулярным]], возможно определение в терминах [[Алгебра|линейной алгебры]] на основе собственных значений [[Матрица смежности графа|матрицы смежности]] <tex>A = A(G)</tex> графа <tex>G</tex>, где <tex>A_{ij}</tex> {{---}} число дуг между вершинами <tex>i</tex> и <tex>j</tex>. Поскольку <tex>A</tex> является симметричной, согласно спектральной теореме<ref>[https[wikipedia://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B5%D0%BA%D1%82%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0Spectral theorem|Wikipedia {{---}} спектральная теорема]]</ref>, <tex>A</tex> имеет <tex>n</tex> действительных собственных значений <tex>\lambda_{1} \ge \lambda_{2} \ge \cdots \ge \lambda_{n}</tex>. Известно, что эти значения лежат в промежутке <tex>[-d, d]</tex>.
Граф регулярен тогда и только тогда, когда вектор <tex>u\in \mathbb {R} ^{n}</tex> с <tex>u_{i}=1</tex> для всех <tex>i = 1 \ldots n</tex> является собственным вектором матрицы <tex>A</tex>, а его собственное число будет постоянной степенью графа. Таким образом, мы имеем <tex>Au = du</tex>, и <tex>u</tex> — собственный вектор матрицы <tex>A</tex> с собственными значениями <tex>\lambda_{1} = d</tex>, где <tex>d</tex> — степень вершин графа <tex>G</tex>. Спектральный зазор графа <tex>G</tex> определяется как <tex>d-\lambda_{2}</tex> и является мерилом спектрального расширения графа <tex>G</tex>.
{{---}} евклидова норма вектора <tex>v\in \mathbb {R} ^{n}</tex>.
Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица <tex>{\tfrac frac {1}{d}}A</tex>, являющаяся матрицей переходов графа G. Все её собственные значения лежат между <tex>-1</tex> и <tex>1</tex>. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения [[Матрица Кирхгофа|матрицы Кирхгофа]]. Для направленного графа используются сингулярные значения матрицы сопряжения A, которые равны квадратным корням из собственных значений симметричной матрицы <tex>A^TA</tex>.
==Конструирование==
Существуют три основные стратегии создания семейств графов расширений. Первая стратегия — алгебраическая и теоретико-групповая, вторая — аналитическая, использующая аддитивную комбинаторику, и третья — комбинаторная, использующая зигзаг-произведение и связанные комбинаторные произведения.
===Маргулис-Габбер-Галил===
[[Алгебра|Алгебраическое]] конструирование, основанное на графах Кэли<ref>https[[wikipedia://en.wikipedia.org/wiki/Cayley_graph|Wikipedia {{---}} граф Кэли]]</ref>, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером и Галилом <ref>[Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291]</ref>. Для любого натурального <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>
Первоначально интерес к экспандерам возник с целью построения устойчивой сети (телефонов или компьютеров) — число дуг графов расширения с ограниченным значением регулярности растет линейно по отношению к числу вершин.
Экспандеры нашли широкое применение в теории вычислительных машин и систем, для построения алгоритмов, в корректирующих кодах<ref>[https[wikipedia://en.wikipedia.org/wiki/Expander_code|Wikipedia {{---}} корректирующие коды]]</ref>, экстракторах, генераторах псевдослучайных чисел<ref>[https[wikipedia://en.wikipedia.org/wiki/Pseudorandom_number_generator|Wikipedia {{---}} генератор псевдослучайных чисел]]</ref>, сетях сортировки<ref>[https[wikipedia://en.wikipedia.org/wiki/Sorting_network|Wikipedia {{---}} ?]</ref> и компьютерных сетях<ref>[https[wikipedia://en.wikipedia.org/wiki/Computer_network|Wikipedia {{---}} компьютерные сети]]</ref>. Они также используются для доказательства многих важных результатов в теории вычислительной сложности, таких как ''SL''<ref>[https://en.wikipedia.org/wiki/SL_(complexity)]</ref>=''L''<ref>[Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — Т. 55, вып. 4. — DOI:10.1145/1391289.1391291]</ref> и Теорема PCP<ref>[Irit Dinur The PCP theorem by gap amplification // Journal of the ACM. — 2007. — Т. 54, вып. 3. — С. 12. — DOI:10.1145/1236457.1236459]</ref>. В криптографии экспандеры используются для создания [[Универсальное семейство хеш-функций|хеш-функций]].
===Лемма о перемешивании===
Лемма о перемешивании утверждает, что для любых двух подмножеств вершин <tex>S,T\subseteq V</tex> число рёбер между <tex>S</tex> и <tex>T</tex> примерно равно числу рёбер в случайном <tex>d</tex>-регулярном графе. Приближение тем лучше, чем меньше <tex>\lambda =\max\{|\lambda _{2}|</tex>,<tex>|\lambda _{n}|\}</tex>. В случайном <tex>d</tex>-регулярном графе, также как и в случайном графе Эрдёша — Реньи<ref>[https[wikipedia://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_modelErdős–Rényi model|Wikipedia {{---}} Erdős–Rényi model]</ref> с вероятностью <tex>{\tfrac {d}{n}}</tex> выбора ребра, ожидается <tex>{\tfrac {d}{n}}\cdot |S|\cdot |T|</tex> рёбер между <tex>S</tex> и <tex>T</tex>.
Более формально, пусть <tex>E(S, T)</tex> обозначает число рёбер между <tex>S</tex> и <tex>T</tex>. Если эти два множества пересекаются, дуги в пересечении считаются дважды, так что
где <tex>\lambda </tex> — абсолютное значение нормализованного второго по величине собственного значения.
Недавно Билу (Bilu) и Линайл (Linial) показали, что обратное тоже верно, то есть, при условии выполнения неравенства из леммы второе по величине собственное значение равно <tex>O(d\lambda \cdot (1+\log(1/\lambda )))</tex><ref>[[http://www.cs.huji.ac.il/~nati/PAPERS/raman_lift.pdf|Lifts, discrepancy and nearly optimal spectral gap]]</ref>.
===Блуждания по экспандеру===
Согласно границе Чернова<ref>[https[wikipedia://en.wikipedia.org/wiki/Chernoff_bound|Wikipedia {{---}} граница Чернова]]</ref>, если выбирать много независимых случайных значений из интервала <tex>[-1, 1]</tex>, с большой степенью вероятности среднее выбранных значений будет близко к [[Математическое ожидание случайной величины|математическому ожиданию]] случайной переменной. Лемма о блуждании по экспандеру, согласно статьям Аджтари, Комлоша и Семереди<ref>[M. Ajtai,J. Komlós,E. Szemerédi Proceedings of the 19th Annual ACM Symposium on Theory of Computing // ACM. — 1987. — С. 132–140. — ISBN 0-89791-221-7. — DOI:10.1145/28395.28410]</ref> и Гилмана<ref>[D. Gillman A Chernoff Bound for Random Walks on Expander Graphs // SIAM Journal on Computing. — Society for Industrial and Applied Mathematics, 1998. — Т. 27, вып. 4,. — С. 1203–1220. — DOI:10.1137/S0097539794268765]</ref>, утверждает, что то же самое верно и для блужданий по экспандеру. Это полезно в теории дерандомизации<ref>[https[wikipedia://en.wikipedia.org/wiki/Randomized_algorithm|Wikipedia {{---}} теория дерандомизации]</ref>, поскольку блуждание по экспандеру использует много меньше случайных бит, чем случайная независимая выборка.
== См. также ==
