Збільшувач (теорія графів)
Збільшувач або експандер (від англ. expander graph — збільшувальний граф) — сильнозв'язний розріджений граф, при цьому зв'язність може визначатися за вершинами, дугами або спектром (див. нижче)[1].
Історія[ред. | ред. код]
Вивчення збільшувачів започаткували московські математики М. С. Пінскер , Л. О. Басалиго та Г. О. Маргуліс у 1970-ті роки. Відтоді ці графи знайшли багато несподіваних застосувань, наприклад, у теорії складності обчислень і теорії кодування. Вони також пов'язані з далекими від класичної теорії графів розділами сучасної математики, наприклад, з теорією груп і теорією чисел, і нині є предметом активних досліджень математиків. Бібліографія на цю тему налічує сотні публікацій[2].
Визначення[ред. | ред. код]
Збільшувач (експандер) — це скінченний ненапрямлений мультиграф, у якому будь-яка не «надто велика» підмножина вершин має сильну зв'язність. Різні формалізації цих понять дають різні типи збільшувачів: реберний збільшувач, вершинний збільшувач і спектральний збільшувач.
Незв'язний граф не є збільшувачем. Будь-який зв'язний граф є збільшувачем, однак різні зв'язні графи мають різні параметри збільшувача. Повний граф має найкращі параметри збільшувача, але він має найбільший можливий степінь. Неформально кажучи, граф є хорошим збільшувачем, якщо він має низький степінь та високий параметр збільшувача.
Реберне збільшення[ред. | ред. код]
Реберне збільшення (також ізопериметричне число або стала Чіґера) графа для вершин визначається як
де мінімум береться за всіма непорожніми множинами не більше ніж вершин і — межові дуги множини , тобто множина дуг з єдиною вершиною в [3].
Вершинне збільшення[ред. | ред. код]
Вершинне ізопериметричне число (також вершинне збільшення) графа визначається як
де — зовнішня межа , тобто множина вершин , що мають принаймні одного сусіда в [4]. У варіанті цього визначення (який називають унікальним сусіднім збільшенням) замінюють множиною вершин з з рівно одним сусідом із [5].
Вершинне ізопериметричне число графа визначається як
де — внутрішня межа , тобто множина вершин , що мають принаймні одного сусіда у [4].
Спектральне збільшення[ред. | ред. код]
Якщо є d-регулярним, можливе визначення в термінах лінійної алгебри на основі власних значень матриці суміжності графа , де — число дуг між вершинами та [6]. Оскільки симетрична, відповідно до спектральної теореми, має дійсних власних значень . Відомо, що ці значення лежать у проміжку .
Граф регулярний тоді й лише тоді, коли вектор з для всіх є власним вектором матриці , а його власне число буде сталим степенем графа. Отже, маємо , і — власний вектор матриці зі власними значеннями , де — степінь вершин графа . Спектральний зазор графа визначається як і є мірою спектрального збільшення графа [7].
Відомо, що тоді й лише тоді, коли — двочастковий. У багатьох випадках, наприклад, в лемі про перемішування необхідно обмежити знизу не тільки зазор між і , але й зазор між і другим із найбільших за модулем власних значень:
- .
Оскільки це власне значення відповідає деякому власному вектору, ортогональному , його можна визначити, використовуючи відношення Релея:
де
— евклідова норма вектора .
Нормалізована версія цього визначення також широко використовується і зручніша для отримання певних результатів. У такому разі розглядається матриця , що є матрицею переходів графа . Усі її власні значення лежать між −1 та 1. Якщо граф не регулярний, спектр графа можна визначити аналогічно, використовуючи власні значення матриці Кірхгофа. Для напрямленого графа використовують сингулярні значення матриці суміжності , які дорівнюють квадратним кореням із власних значень симетричної матриці .
Взаємозв'язок різних видів збільшення[ред. | ред. код]
Згадані вище види збільшення взаємопов'язані. Зокрема, для будь-якого -регулярного графа ,
Отже, для графів сталого степеня, вершинне та реберне збільшення рівні за величиною.
Нерівності Чіґера[ред. | ред. код]
У випадку, коли є -регулярним графом, є співвідношення між і спектральним зазором графа . Нерівність, яку отримали Таннер (Tanner) і, незалежно, Алон (Noga Alon) та Мільман (Vitali Milman)[8], стверджує, що[9]
Ця нерівність тісно пов'язана з межею Чіґера[en] для ланцюгів Маркова і може розглядатися як дискретна версія нерівності Чіґера в геометрії Рімана.
Вивчається також схожий зв'язок між вершинними ізопериметричними числами та спектральним зазором[10] . Зауважимо, що в статті відповідає тут
Асимптотично числа , і обмежені зверху спектральним зазором .
Побудови[ред. | ред. код]
Існують три основні стратегії створення сімейств графів-збільшувачів[11]. Перша стратегія — алгебрична і теоретико-групова, друга — аналітична, з використанням адитивної комбінаторики, і третя — комбінаторна, що використовує зигзаг-добуток і пов'язані комбінаторні добутки.
Маргуліс — Габбер — Галіл[ред. | ред. код]
Алгебричне конструювання, засноване на графах Келі, відоме для різних варіантів збільшувачів. Розглянемо конструювання, яке запропонував Маргуліс і проаналізували Габером (Gabber) та Галілом (Galil)[12]. Для будь-якого натурального будуємо граф, зі множиною вершин , де . Для будь-якої вершини , її вісім сусідів будуть
Виконується така теорема:
Теорема. Для всіх друге за величиною власне значення графа задовольняє нерівності .
Граф Рамануджана[ред. | ред. код]
За теоремою Алона і Боппана (Boppana) для всіх досить великих -регулярних графів виконується нерівність , де — друге за абсолютною величиною власне число[13]. Для графів Рамануджана [14]. Таким чином, графи Рамануджана мають асимптотично найменше можливе значення і є чудовими спектральними збільшувачами.
Олександр Любоцький, Філіпс та Сарнак (1988), Маргуліс (1988) та Моргенштерн (1994) показали як можна явно сконструювати граф Рамануджана[15]. За теоремою Фрідмана (Friedman, 2003) випадковий -регулярний граф[en] з вершинами є майже графом Рамануджана, оскільки виконується
з імовірністю при [16].
Застосування та корисні властивості[ред. | ред. код]
Спочатку інтерес до збільшувачів виник з метою побудови стійкої мережі (телефонів або комп'ютерів) — число дуг графів-збільшувачів з обмеженим значенням регулярності зростає лінійно відносно числа вершин.
Експандери знайшли широке застосування в теорії обчислювальних машин і систем, для побудови алгоритмів, в коригувальних кодах[en], екстракторах[en], генераторах псевдовипадкових чисел, сортувальних мережах[en][17] та комп'ютерних мережах . Їх також використовують для доведення багатьох важливих результатів теорії обчислювальної складності, таких як SL[en] = L[18] і теорема PCP[19]. У криптографії збільшувачі використовуються для створення хеш-функцій.
Нижче наведено деякі властивості експандерів, які вважають корисними в багатьох галузях.
Лемма про перемішування[ред. | ред. код]
Лемма про перемішування стверджує, що для будь-яких двох підмножин вершин число ребер між і приблизно дорівнює числу ребер у випадковому -регулярному графі. Наближення тим краще, чим менше . У випадковому -регулярному графі, як і у випадковому графі Ердеша — Реньї з імовірністю вибору ребра, очікується ребер між і .
Формальніше, нехай позначає число ребер між і . Якщо ці дві множини перетинаються, дуги в перетині враховуються двічі, так що
- .
Лемма про перемішування стверджує, що[20]
де — абсолютне значення нормалізованого другого за величиною власного значення.
Нещодавно Білу (Bilu) і Лінайл (Linial) показали, що обернене теж істинне, тобто, за умови виконання нерівності з леми, друге за величиною власне значення дорівнює [21].
Блукання збільшувачем[ред. | ред. код]
Відповідно до межі Чернова, якщо вибирати багато незалежних випадкових значень з інтервалу [−1, 1], з великим ступенем імовірності середнє вибраних значень буде близьким до математичного сподівання випадкової змінної. Лемма про блукання збільшувачем, згідно зі статтями Аджтарі, Комлоша і Семереді[22] і Гілмана[23], стверджує, що те саме виконується і для блукань збільшувачем. Це корисно в теорії дерандомізації, оскільки блукання збільшувачем використовує значно менше випадкових бітів, ніж випадкова незалежна вибірка.
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
- ↑ AMS, 2006.
- ↑ Гашков, 2009.
- ↑ AMS, 2006, Визначення 2.1.
- ↑ а б Bobkov, 2000.
- ↑ AlonCapalbo, 2002.
- ↑ AMS, 2006, розділ 2.3.
- ↑ AMS, 2006, Визначення спектрального зазору взято з розділу 2.3.
- ↑ AlonSpencer, 2011.
- ↑ AMS, 2006, Теорема 2.4.
- ↑ Bobkov, 2000, Теорема 1 на стор. 156.
- ↑ Yehudayoff, 2012.
- ↑ Goldreich, 2011, див., наприклад, стор. 9.
- ↑ AMS, 2006, Теорема 2.7.
- ↑ AMS, 2006, Визначення 5.11.
- ↑ AMS, 2006, Теорема 5.12.
- ↑ AMS, 2006, Теорема 7.10.
- ↑ ACM, 1983.
- ↑ Reingold, 2008.
- ↑ Dinur, 2007.
- ↑ Пояснення леми про перемішування.
- ↑ Твердження, обернене до леми про перемішування.
- ↑ ACM, 1987.
- ↑ Gillman, 1998.
Література[ред. | ред. код]
- Книги
- С. Б. Гашков. Графы-расширители и их применения в теории кодирования. — М. : МЦНМО, 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: .
- Bobkov S., Houdré C., Tetali P. λ∞, vertex isoperimetry and concentration // Combinatorica. — 2000. — Т. 20, вип. 2. — С. 153–172. — DOI: ..
- 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: .
- 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: .
- Irit Dinur. The PCP theorem by gap amplification // Journal of the ACM. — Т. 54, вип. 3. — С. 12. — DOI: ..
- 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: .
- Oded Goldreich. Basic Facts about Expander Graphs // Studies in Complexity and Cryptography. — 2011. — С. 451–464. — DOI: .
- Omer Reingold. Undirected connectivity in log-space // Journal of the ACM. — Т. 55, вип. 4. — DOI: .
- Yehudayoff, Amir. Proving expansion in three steps. — 2012. — Т. 43, вип. 3. — С. 67–84. — DOI: .