Экспандер (теория графов)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В комбинаторике экспандером (или расширяющим графом, expander graph) называется сильно связанный разреженный граф, при этом связность определяется по вершинам, дугам или спектру (смотрите ниже)[1].

Экспандеры — это класс графов, изучение которых первыми начали московские математики М. С. Пинскер, Л. А. Бассалыго и Г. А. Маргулис в семидесятые годы прошлого века. За прошедшее время эти графы нашли много неожиданных применений, например в теории сложности вычислений и в теории кодирования. Загадочным образом они оказались также связаны с далекими от классической теории графов разделами современной математики, например, с теорией групп и теорией чисел, и являются в настоящее время предметом активных исследований, ведущихся в основном зарубежными математиками. Библиография по этой теме насчитывает сотни публикаций[2].

Определение[править | править вики-текст]

Экспандер — это конечный ненаправленный мультиграф, в котором любое подмножество вершин, не являясь «слишком большим», имеет «сильную» связность. Различные формализации этих понятий дают различные типы экспандеров: рёберный расширитель, вершинный расширитель, и спектральный расширитель.

Несвязный граф не является экспандером. Любой связный граф является экспандером, однако различные связные графы имеют различные параметры расширителя. Полный граф имеет лучшие параметры расширителя, но имеет наибольшую возможную степень. Неформально говоря, граф является хорошим экспандером, если он имеет низкую степень и высокий параметр расширителя.

Рёберное расширение[править | править вики-текст]

Рёберное расширение (также изопериметрическое число или константа Чигера) h(G) графа G для n вершин определяется как

h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial(S)|}{|S|},

где минимум берётся по всем непустым множествам S не более чем n/2 вершин и ∂(S) — граничные дуги множества S, то есть, множество дуг с единственной вершиной в S [1].

Вершинное расширение[править | править вики-текст]

Вершинное изопериметрическое число h_{\text{out}}(G) (также вершинное раширение) графа G определяется как

h_{\text{out}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|},

где \partial_{\text{out}}(S) — внешняя граница S, то есть множество вершин из V(G)\setminus S, имеющих как минимум одного соседа в S [3]. В варианте этого определения (называемом уникальным соседним расширением) \partial_{\text{out}}(S) заменяется на множество вершин из V с точностью одним соседом из S[4].

Вершинное изопериметрическое число h_{\text{in}}(G) графа G определяется как

h_{\text{in}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{in}}(S)|}{|S|},

где \partial_{\text{in}}(S) — внутренняя граница S, то есть множество вершин S, имеющих как минимум одного соседа в V(G)\setminus S [3].

Спектральное расширение[править | править вики-текст]

Если G является d-регулярным, возможно определение в терминах линейной алгебры на основе собственных значений матрицы смежности A = A(G) графа G, где A_{ij} — число дуг между вершинами i и j [1]. Поскольку A является симметричной, согласно спектральной теореме, A имеет n действительных собственных значений \lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_{n}. Известно, что эти значения лежат в промежутке [−d, d].

Граф регулярен тогда и только тогда, когда вектор u\in\R^n с u_i=1 для всех i = 1, …, n является собственным вектором матрицы A, а его собственное число будет постоянной степенью графа. Таким образом, мы имеем Au = du, и u — собственный вектор матрицы A с собственными значениями λ1 = d, где d — степень вершин графа G. Спектральный зазор графа G определяется как d−λ2 и является мерилом спектрального расширения графа G [1].

Известно, что λn = −d тогда и только тогда, когда G — двудольный. Во многих случаях, например в лемме о перемешивании, необходимо ограничить снизу не только зазор между λ1 и λ2, но и зазор между λ1 и вторым максимальным по модулю собственным значением:

\lambda=\max\{|\lambda_2|, |\lambda_{n}|\}.

Поскольку это собственное значение соответствует некоторому собственному вектору, ортогональному u, его можно определить, используя отношение Рэлея:

\lambda=\max_{0\neq v\perp u} \frac{\|Av\|_2}{\|v\|_2},

где

\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1/2}

евклидова норма вектора v\in\R^n.

Нормализованная версия этого определения также широко используется и более удобна для получения определённых результатов. В таком случае рассматривается матрица \tfrac{1}{d} A, являющаяся матрицей переходов графа G. Все её собственные значения лежат между −1 и 1. Если граф не регулярен, спектр графа может быть определён аналогичным образом, используя собственные значения матрицы Кирхгофа. Для направленного графа используются сингулярные значения матрицы сопряжения A, которые равны квадратным корням из собственных значений симметричной матрицы ATA.

Взаимосвязь различных видов расширения[править | править вики-текст]

Вышеупомянутые виды расширения взаимосвязаны. В частности, для любого d-регулярного графа G,

h_{\text{out}}(G) \le h(G) \le d \cdot h_{\text{out}}(G).

Следовательно, для графов постоянной степени, вершинное и рёберное расширение равны по величине.

Неравенства Чигера[править | править вики-текст]

В случае, когда G является d-регулярным графом, имеется соотношение между h(G) и спектральным зазором d − λ2 графа G. Неравенство, полученное Таннером (Tanner) и, независимо, Алоном (Noga Alon) и Мильманом (Vitali Milman)[5], утверждает, что[1]

\tfrac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}.

Это неравенство тесно связано с границей Чигера[en] для цепей Маркова и может рассматриваться как дискретная версия неравенства Чигера в геометрии Римана.

Изучается также похожая связь между вершинными изопериметрическими числами и спектральным зазором[3]. Заметим, что λ2 в статье соответствует 2(d − λ2) здесь

h_{\text{out}}(G)\le \left(\sqrt{4 (d-\lambda_2)} + 1\right)^2 -1
h_{\text{in}}(G) \le \sqrt{8(d-\lambda_2)}.

Асимптотически числа \frac{h^2}{d}, h_{\text{out}} и h_{\text{in}}^2 ограничены сверху спектральным зазором O(d-\lambda_2).

Конструирование[править | править вики-текст]

Существуют три основные стратегии создания семейств графов расширений[6]. Первая стратегия — алгебраическая и теоретико-групповая, вторая — аналитическая, использующая аддитивную комбинаторику, и третья — комбинаторная, использующая зигзаг-произведение и связанные комбинаторные произведения.

Маргулис-Габбер-Галил[править | править вики-текст]

Алгебраическое конструирование, основанное на графах Кэли, известно для различных вариантов экспандеров. Следующее конструирование принадлежит Маргулису и было проанализировано Габбером (Gabber) и Галилом (Galil)[7]. Для любого натурального n строим граф, Gn со множеством вершин \mathbb Z_n \times \mathbb Z_n, где \mathbb Z_n=\mathbb Z/n\mathbb Z. Для любой вершины (x,y)\in\mathbb Z_n \times \mathbb Z_n, её восемь соседей будут

(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).

Выполняется следующая теорема:

Теорема. Для всех n граф Gn второе по величине собственное число \lambda(G)\leq 5 \sqrt{2}.

Граф Рамануджана[править | править вики-текст]

По теореме Алона (Alon) и Боппана (Boppana) для всех достаточно больших d-регулярных графов выполняется неравенство \lambda \ge 2\sqrt{d-1} - o(1), где λ — второе по абсолютной величине собственное число[1]. Для графов Рамануджана[en]\lambda \le 2\sqrt{d-1} [1]. Таким образом, графы Рамануджана имеют асимптотически наименьшее возможное значение λ и являются превосходными спектральными расширителями.

Александр Любоцкий, Филипс и Сарнак (1988), Маргулис (1988) и Моргенштерн (1994) показали как можно явно сконструировать граф Рамануджана[1]. По теореме Фридмана (Friedman,2003) случайный d-регулярный граф[en] с n вершинами является почти графом Рамануджана, поскольку выполняется

\lambda \le 2\sqrt{d-1}+\epsilon

с вероятностью 1-o(1) при n \rightarrow \infty [1].

Приложения и полезные свойства[править | править вики-текст]

Первоначально интерес к экспандерам возник с целью построения устойчивой сети (телефонов или компьютеров) — число дуг графов расширения с ограниченным значением регулярности растет линейно по отношению к числу вершин.

Экспандеры нашли широкое применение в теории вычислительных машин и систем, для построения алгоритмов, в корректирующих кодах[en], экстракторах[en], генераторах псевдослучайных чисел, сетях сортировки[8] и компьютерных сетях. Они также используются для доказательства многих важных результатов в теории вычислительной сложности, таких как SL[en]=L[en][9] и Теорема PCP[10]. В rриптографии экспандеры используются для создания хеш-функций.

Ниже приведены некоторые свойства экспандеров, считающиеся полезными во многих областях.

Лемма о перемешивании[править | править вики-текст]

Лемма о перемешивании утверждает, что для любых двух подмножеств вершин S, T \subseteq V число рёбер между S и T примерно равно числу рёбер в случайном d-регулярном графе. Приближение тем лучше, чем меньше \lambda=\max\{|\lambda_2|,|\lambda_n|\}. В случайном d-регулярном графе, также как и в случайном графе Эрдёша — Реньи[en]с вероятностью \tfrac{d}{n} выбора ребра, ожидается \tfrac{d}{n} \cdot |S| \cdot |T| рёбер между S и T.

Более формально, пусть E(S, T) обозначает число рёбер между S и T. Если эти два множества пересекаются, дуги в пересечении считаются дважды, так что

E(S,T)=2|E(G[S\cap T])| + E(S\setminus T,T) + E(S,T\setminus S).

Лемма о перемешивании утверждает, что[11]

\left|E(S, T) - \frac{d \cdot |S| \cdot |T|}{n}\right| \leq d\lambda  \sqrt{|S| \cdot |T|},

где λ — абсолютное значение нормализованного второго по величине собственного значения.

Недавно Билу (Bilu) и Линайл (Linial) показали, что обратное тоже верно, то есть, при условии выполнения неравенства из леммы второе по величине собственное значение равно O(d \lambda\cdot (1+\log(1/\lambda)))[12].

Блуждания по экспандеру[править | править вики-текст]

Согласно границе Чернова[en], если выбирать много независимых случайных значений из интервала [−1, 1], с большой степенью вероятности среднее выбранных значений будет близко к математическому ожиданию случайной переменной. Лемма о блуждании по экспандеру, согласно статьям Аджтари, Комлоша и Семереди[13] и Гилмана[14], утверждает, что то же самое верно и для блужданий по экспандеру. Это полезно в теории дерандомизации[en], поскольку блуждание по экспандеру использует много меньше случайных бит, чем случайная независимая выборка.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 3 4 5 6 7 8 9 AMS, 2006
  2. Гашков, 2009
  3. 1 2 3 Bobkov, 2000
  4. AlonCapalbo, 2002
  5. AlonSpencer, 2011
  6. Yehudayoff, 2012
  7. Goldreich, 2011
  8. ACM, 1983
  9. Reingold, 2008
  10. Dinur, 2007
  11. Объяснение леммы о перемешивании. [1]
  12. Обратное утверждение к лемме о перемешивании. [2]
  13. ACM, 1987
  14. Gillman, 1998

Литература[править | править вики-текст]

Книги

  • С. Б. Гашков, Графы-расширители и их применения в теории кодирования. — М: МЦНМО, 2009. — С. 70–122. — (Математическое просвещение, третья серия).

Исследовательские статьи

  • Alon, N.; Capalbo, M. Explicit unique-neighbor expanders // The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.. — 2002. — С. 73.
  • Shlomo Hoory, Nathan Linial, Avi Widgerson Expander graphs and their applications // Bulletin (New series) of the American Mathematical Society. — 2006. — В. 4. — Т. 43. — С. 439–561. — DOI:10.1090/S0273-0979-06-01126-8
  • Bobkov S., Houdré C., Tetali P. λ, vertex isoperimetry and concentration // Combinatorica. — 2000. — В. 2. — Т. 20. — С. 153–172. — DOI:10.1007/s004930070018.
  • Miklós Ajtai, János Komlós, Endre Szemerédi Proceedings of the 15th Annual ACM Symposium on Theory of Computing. — 1983. — С. 1–9. — ISBN 0-89791-099-0. — DOI:10.1145/800061.808726
  • 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
  • Irit Dinur The PCP theorem by gap amplification // Journal of the ACM. — 2007. — В. 3. — Т. 54. — С. 12. — DOI:10.1145/1236457.1236459.
  • D. Gillman A Chernoff Bound for Random Walks on Expander Graphs // SIAM Journal on Computing. — Society for Industrial and Applied Mathematics, 1998. — В. 4,. — Т. 27. — С. 1203–1220. — DOI:10.1137/S0097539794268765
  • Oded Goldreich Basic Facts about Expander Graphs // Studies in Complexity and Cryptography. — 2011. — С. 451–464. — DOI:10.1007/978-3-642-22670-0_30
  • Omer Reingold Undirected connectivity in log-space // Journal of the ACM. — 2008. — В. 4. — Т. 55. — DOI:10.1145/1391289.1391291
  • Yehudayoff, Amir Proving expansion in three steps. — 2012. — В. 3. — Т. 43. — С. 67–84. — DOI:10.1145/2421096.2421115

Ссылки[править | править вики-текст]