Збільшувач (теорія графів)

Збільшувач або експандер (від англ. expander graph — збільшувальний граф) — сильнозв'язний розріджений граф, при цьому зв'язність може визначатися за вершинами, дугами або спектром (див. нижче).

Історія

Вивчення збільшувачів започаткували московські математики М. С. Пінскер , Л. О. Басалиго та Г. О. Маргуліс у 1970-ті роки. Відтоді ці графи знайшли багато несподіваних застосувань, наприклад, у теорії складності обчислень і теорії кодування. Вони також пов'язані з далекими від класичної теорії графів розділами сучасної математики, наприклад, з теорією груп і теорією чисел, і нині є предметом активних досліджень математиків. Бібліографія на цю тему налічує сотні публікацій.

Визначення

Збільшувач (експандер) — це скінченний ненапрямлений мультиграф, у якому будь-яка не «надто велика» підмножина вершин має сильну зв'язність. Різні формалізації цих понять дають різні типи збільшувачів: реберний збільшувач, вершинний збільшувач і спектральний збільшувач.

Незв'язний граф не є збільшувачем. Будь-який зв'язний граф є збільшувачем, однак різні зв'язні графи мають різні параметри збільшувача. Повний граф має найкращі параметри збільшувача, але він має найбільший можливий степінь. Неформально кажучи, граф є хорошим збільшувачем, якщо він має низький степінь та високий параметр збільшувача.

Реберне збільшення

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

$h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},$

де мінімум береться за всіма непорожніми множинами $S$ не більше ніж $n/2$ вершин і $\partial (S)$ — межові дуги множини $S$, тобто множина дуг з єдиною вершиною в $S$.

Вершинне збільшення

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

$h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},$

де $\partial _{\text{out}}(S)$ — зовнішня межа $S$, тобто множина вершин $V(G)\setminus S$, що мають принаймні одного сусіда в $S$. У варіанті цього визначення (який називають унікальним сусіднім збільшенням) $\partial _{\text{out}}(S)$ замінюють множиною вершин з $V$ з рівно одним сусідом із $S$.

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

$h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},$

де $\partial _{\text{in}}(S)$ — внутрішня межа $S$, тобто множина вершин $S$, що мають принаймні одного сусіда у $V(G)\setminus S$.

Спектральне збільшення

Якщо $G$ є d-регулярним, можливе визначення в термінах лінійної алгебри на основі власних значень матриці суміжності $A=A(G)$ графа $G$, де $A_{ij}$ — число дуг між вершинами $i$ та $j$. Оскільки $A$ симетрична, відповідно до спектральної теореми, $A$ має $n$ дійсних власних значень $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$. Відомо, що ці значення лежать у проміжку $[-d,d]$$[-d,d]$.

Граф регулярний тоді й лише тоді, коли вектор $u\in \mathbb {R} ^{n}$ з $u_{i}=1$ для всіх $i=1,\ldots ,n$ є власним вектором матриці $A$, а його власне число буде сталим степенем графа. Отже, маємо $Au=du$, і $u$ — власний вектор матриці $A$ зі власними значеннями $\lambda _{1}=d$, де $d$ — степінь вершин графа $G$. Спектральний зазор графа $G$ визначається як $d-\lambda _{2}$ і є мірою спектрального збільшення графа $G$.

Відомо, що $\lambda _{n}=-d$ тоді й лише тоді, коли $G$ — двочастковий. У багатьох випадках, наприклад, в лемі про перемішування необхідно обмежити знизу не тільки зазор між $\lambda _{1}$ і $\lambda _{2}$, але й зазор між $\lambda _{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 \mathbb {R} ^{n}$.

Нормалізована версія цього визначення також широко використовується і зручніша для отримання певних результатів. У такому разі розглядається матриця ${\tfrac {1}{d}}A$, що є матрицею переходів графа $G$. Усі її власні значення лежать між −1 та 1. Якщо граф не регулярний, спектр графа можна визначити аналогічно, використовуючи власні значення матриці Кірхгофа. Для напрямленого графа використовують сингулярні значення матриці суміжності $A$, які дорівнюють квадратним кореням із власних значень симетричної матриці $A^{T}A$.

Взаємозв'язок різних видів збільшення

Згадані вище види збільшення взаємопов'язані. Зокрема, для будь-якого $d$-регулярного графа $G$,

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

Отже, для графів сталого степеня, вершинне та реберне збільшення рівні за величиною.

Нерівності Чіґера

У випадку, коли $G$ є $d$-регулярним графом, є співвідношення між $h(G)$ і спектральним зазором $d-\lambda _{2}$ графа $G$. Нерівність, яку отримали Таннер (Tanner) і, незалежно, Алон (Noga Alon) та Мільман (Vitali Milman), стверджує, що

${\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.$

Ця нерівність тісно пов'язана з межею Чіґера для ланцюгів Маркова і може розглядатися як дискретна версія нерівності Чіґера в геометрії Рімана.

Вивчається також схожий зв'язок між вершинними ізопериметричними числами та спектральним зазором . Зауважимо, що $\lambda _{2}$ в статті відповідає $2(d-\lambda _{2})$ тут

$h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1$

$h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.$

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

Побудови

Існують три основні стратегії створення сімейств графів-збільшувачів. Перша стратегія — алгебрична і теоретико-групова, друга — аналітична, з використанням адитивної комбінаторики, і третя — комбінаторна, що використовує зигзаг-добуток і пов'язані комбінаторні добутки.

Маргуліс — Габбер — Галіл

Алгебричне конструювання, засноване на графах Келі, відоме для різних варіантів збільшувачів. Розглянемо конструювання, яке запропонував Маргуліс і проаналізували Габером (Gabber) та Галілом (Galil). Для будь-якого натурального $n$ будуємо граф, $G_{n}$ зі множиною вершин $\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$ друге за величиною власне значення графа $G_{n}$ задовольняє нерівності $\lambda (G)\leq 5{\sqrt {2}}$ .

Граф Рамануджана

За теоремою Алона і Боппана (Boppana) для всіх досить великих $d$-регулярних графів виконується нерівність $\lambda \geq 2{\sqrt {d-1}}-o(1)$, де $\lambda$ — друге за абсолютною величиною власне число. Для графів Рамануджана $\lambda \leq 2{\sqrt {d-1}}$. Таким чином, графи Рамануджана мають асимптотично найменше можливе значення і є чудовими спектральними збільшувачами.

Олександр Любоцький, Філіпс та Сарнак (1988), Маргуліс (1988) та Моргенштерн (1994) показали як можна явно сконструювати граф Рамануджана. За теоремою Фрідмана (Friedman, 2003) випадковий $d$-регулярний граф з $n$ вершинами є майже графом Рамануджана, оскільки виконується

$\lambda \leq 2{\sqrt {d-1}}+\epsilon$

з імовірністю $1-o(1)$ при $n\rightarrow \infty$.

Застосування та корисні властивості

Спочатку інтерес до збільшувачів виник з метою побудови стійкої мережі (телефонів або комп'ютерів) — число дуг графів-збільшувачів з обмеженим значенням регулярності зростає лінійно відносно числа вершин.

Експандери знайшли широке застосування в теорії обчислювальних машин і систем, для побудови алгоритмів, в коригувальних кодах, екстракторах, генераторах псевдовипадкових чисел, сортувальних мережах та комп'ютерних мережах . Їх також використовують для доведення багатьох важливих результатів теорії обчислювальної складності, таких як SL = L і теорема PCP. У криптографії збільшувачі використовуються для створення хеш-функцій.

Нижче наведено деякі властивості експандерів, які вважають корисними в багатьох галузях.

Лемма про перемішування

Лемма про перемішування стверджує, що для будь-яких двох підмножин вершин $S,T\subseteq V$ число ребер між $S$ і $T$ приблизно дорівнює числу ребер у випадковому $d$-регулярному графі. Наближення тим краще, чим менше $\lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}$. У випадковому $d$-регулярному графі, як і у випадковому графі Ердеша — Реньї з імовірністю ${\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)$ .

Лемма про перемішування стверджує, що

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

де $\lambda$ — абсолютне значення нормалізованого другого за величиною власного значення.

Нещодавно Білу (Bilu) і Лінайл (Linial) показали, що обернене теж істинне, тобто, за умови виконання нерівності з леми, друге за величиною власне значення дорівнює $O(d\lambda \cdot (1+\log(1/\lambda )))$.

Блукання збільшувачем

Відповідно до межі Чернова, якщо вибирати багато незалежних випадкових значень з інтервалу [−1, 1], з великим ступенем імовірності середнє вибраних значень буде близьким до математичного сподівання випадкової змінної. Лемма про блукання збільшувачем, згідно зі статтями Аджтарі, Комлоша і Семереді і Гілмана, стверджує, що те саме виконується і для блукань збільшувачем. Це корисно в теорії дерандомізації, оскільки блукання збільшувачем використовує значно менше випадкових бітів, ніж випадкова незалежна вибірка.

Див. також

• Алгебраїчна зв'язність
• Зигзаг-добуток

Література

Книги

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

• Noga Alon, Joel Spencer. The Probabilistic Method. — 3rd. — John Wiley & Sons, 2011.
• Chung, Fan R. K. Spectral Graph Theory. — American Mathematical Society, 1997. — Т. 92. — (CBMS Regional Conference Series in Mathematics) — ISBN 0-8218-0315-8.
• Guiliana Davidoff, Peter Sarnak, Alain Valette. Elementary number theory, group theory and Ramanujan graphs. — Cambridge University Press, 2003. — Т. 55. — (LMS student texts) — ISBN 0-521-53143-8.
• Mike Krebs, Anthony. Expander families and Cayley graphs: A beginner's guide. — Oxford University Press, 2011. — ISBN 0-19-976711-4.

Статті

• 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. — Т. 43, вип. 4. — С. 439–561. — DOI:10.1090/S0273-0979-06-01126-8.
• Bobkov S., Houdré C., Tetali P. λ_∞, vertex isoperimetry and concentration // Combinatorica. — 2000. — Т. 20, вип. 2. — С. 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. — Т. 54, вип. 3. — С. 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. — Т. 27, вип. 4,. — С. 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. — Т. 55, вип. 4. — DOI:10.1145/1391289.1391291.
• Yehudayoff, Amir. Proving expansion in three steps. — 2012. — Т. 43, вип. 3. — С. 67–84. — DOI:10.1145/2421096.2421115.

Посилання

• Brief introduction в Notices of the American Mathematical Society
• Introductory paper by Michael Nielsen
• Lecture notes from a course on expanders (Nati Linial and Avi Wigderson)
• Lecture notes from a course on expanders (Для Prahladh Harsha)
• Definition and application of spectral gap