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

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

Історія

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Граф регулярний тоді й лише тоді, коли вектор $u\in {ℝ}^n$ з $u_i=1$ для всіх $i=1,\dots ,n$ є власним вектором матриці $A$, а його власне число буде сталим степенем графа. Отже, маємо $Au=du$, і $u$ — власний вектор матриці $A$ зі власними значеннями ${\lambda }_1=d$, де $d$ — степінь вершин графа $G$. Спектральний зазор графа $G$ визначається як $d-{\lambda }_2$ і є мірою спектрального збільшення графа $G$Шаблон:Sfn.

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

$\lambda =\max \{|{\lambda }_2|,|{\lambda }_n|\}$ .

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

$\lambda =\underset{0\ne v\perp u}{\max }\frac{\Vert Av{\Vert }_2}{\Vert v{\Vert }_2},$

де

$\Vert v{\Vert }_2={\left(\sum _{i=1}^n{v}_i^2\right)}^{1/2}$

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

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

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

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

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

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

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

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

$\frac{1}{2}(d-{\lambda }_2)\le h(G)\le \sqrt{2d(d-{\lambda }_2)}.$

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

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

$h_{\text{out}}(G)\le {(\sqrt{4(d-{\lambda }_2)}+1)}^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)$.

Побудови

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

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

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

.

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

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

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

$\lambda \le 2\sqrt{d-1}+ϵ$

з імовірністю $1-o(1)$ при $n\to \mathrm{\infty }$Шаблон:Sfn.

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Література

Книги

• Шаблон:Книга

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Статті

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття.
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття.
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття

Посилання

• 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