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

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

Історія

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Відомо, що ${\displaystyle \lambda _{n}=-d}$ тоді й лише тоді, коли ${\displaystyle G}$ — двочастковий. У багатьох випадках, наприклад, в лемі про перемішування необхідно обмежити знизу не тільки зазор між ${\displaystyle \lambda _{1}}$ і ${\displaystyle \lambda _{2}}$, але й зазор між ${\displaystyle \lambda _{1}}$ і другим із найбільших за модулем власних значень:

${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}$ .

Оскільки це власне значення відповідає деякому власному вектору, ортогональному ${\displaystyle u}$, його можна визначити, використовуючи відношення Релея:

${\displaystyle \lambda =\max _{0\neq v\perp u}{\frac {\|Av\|_{2}}{\|v\|_{2}}},}$

де

${\displaystyle \|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}}$

— евклідова норма вектора ${\displaystyle v\in \mathbb {R} ^{n}}$.

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

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

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

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

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

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

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

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

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

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

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

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

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

Побудови

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

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

Алгебричне конструювання, засноване на графах Келі, відоме для різних варіантів збільшувачів. Розглянемо конструювання, яке запропонував Маргуліс і проаналізували Габером (Gabber) та Галілом (Galil). Для будь-якого натурального ${\displaystyle n}$ будуємо граф, ${\displaystyle G_{n}}$ зі множиною вершин ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$, де ${\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }$ . Для будь-якої вершини ${\displaystyle (x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$, її вісім сусідів будуть

${\displaystyle (x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).}$

Виконується така теорема:

Теорема. Для всіх ${\displaystyle n}$ друге за величиною власне значення графа ${\displaystyle G_{n}}$ задовольняє нерівності ${\displaystyle \lambda (G)\leq 5{\sqrt {2}}}$ .

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

Докладніше: Граф Рамануджана

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

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

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

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

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

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

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

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

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

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

Формальніше, нехай ${\displaystyle E(S,T)}$ позначає число ребер між ${\displaystyle S}$ і ${\displaystyle T}$. Якщо ці дві множини перетинаються, дуги в перетині враховуються двічі, так що

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

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

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

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

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

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

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

Див. також

• Алгебраїчна зв'язність

Примітки

1. AMS, 2006.
2. Гашков, 2009.
3. AMS, 2006, Визначення 2.1.
4. Bobkov, 2000.
5. AlonCapalbo, 2002.
6. AMS, 2006, розділ 2.3.
7. AMS, 2006, Визначення спектрального зазору взято з розділу 2.3.
8. AlonSpencer, 2011.
9. AMS, 2006, Теорема 2.4.
10. Bobkov, 2000, Теорема 1 на стор. 156.
11. Yehudayoff, 2012.
12. Goldreich, 2011, див., наприклад, стор. 9.
13. AMS, 2006, Теорема 2.7.
14. AMS, 2006, Визначення 5.11.
15. AMS, 2006, Теорема 5.12.
16. AMS, 2006, Теорема 7.10.
17. ACM, 1983.
18. Reingold, 2008.
19. Dinur, 2007.
20. Пояснення леми про перемішування.
21. Твердження, обернене до леми про перемішування.
22. ACM, 1987.
23. Gillman, 1998.

Література

Книги

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

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

Статті

• 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. — . — 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. — . — 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 // . — Т. 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 (Для Prahladh Harsha)