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

В математической области спектральной теории графов граф Рамануджана — это регулярный граф , спектральный зазор которого почти максимально велик (см. экстремальную теорию графов ). Такие графы являются превосходными спектральными расширителями . Как отмечается в обзорной статье Мурти ^[1] , графы Рамануджана «объединяют различные ветви чистой математики, а именно, теорию чисел , теорию представлений и алгебраическую геометрию ». Эти графы косвенно названы в честь Шринивасы Рамануджана ; их название происходит от гипотезы Рамануджана–Петерссона , которая использовалась при построении некоторых из этих графов.

Определение

Пусть будет связным -регулярным графом с вершинами, и пусть будут собственными значениями матрицы смежности ( или спектра ) . Поскольку является связным и -регулярным, его собственные значения удовлетворяют . ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle d=\lambda _{1}>\lambda _{2}}$ ${\displaystyle \geq \cdots \geq \lambda _{n}\geq -d}$

Определим . Связный -регулярный граф является графом Рамануджана, если . ${\displaystyle \lambda (G)=\max _{i\neq 1}|\lambda _{i}|=\max(|\lambda _{2}|,\ldots ,|\lambda _{n}|)}$ ${\displaystyle d}$ ${\displaystyle G}$ ${\displaystyle \lambda (G)\leq 2{\sqrt {d-1}}}$

Во многих источниках используется альтернативное определение (всякий раз, когда существует с ) для определения графов Рамануджана. ^[2] Другими словами, мы допускаем в дополнение к «малым» собственным значениям. Так как тогда и только тогда, когда граф является двудольным , мы будем ссылаться на графы, которые удовлетворяют этому альтернативному определению, но не первому определению двудольные графы Рамануджана . Если — граф Рамануджана, то — двудольный граф Рамануджана, поэтому существование графов Рамануджана сильнее. ${\displaystyle \lambda '(G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|}$ ${\displaystyle \lambda _{i}}$ ${\displaystyle |\lambda _{i}|<d}$ ${\displaystyle -d}$ ${\displaystyle \lambda _{n}=-d}$ ${\displaystyle G}$ ${\displaystyle G\times K_{2}}$

Как заметил Тошиказу Сунады , регулярный граф является графом Рамануджана тогда и только тогда, когда его дзета-функция Ихара удовлетворяет аналогу гипотезы Римана . ^[3]

Примеры и конструкции

Явные примеры

• Полный граф имеет спектр , и, следовательно , и граф является графом Рамануджана для каждого . Полный двудольный граф имеет спектр , и, следовательно, является двудольным графом Рамануджана для каждого . ${\displaystyle K_{d+1}}$ ${\displaystyle d,-1,-1,\dots ,-1}$ ${\displaystyle \lambda (K_{d+1})=1}$ ${\displaystyle d>1}$ ${\displaystyle K_{d,d}}$ ${\displaystyle d,0,0,\dots ,0,-d}$ ${\displaystyle d}$
• Граф Петерсена имеет спектр , поэтому он является 3-регулярным графом Рамануджана. Икосаэдрический граф является 5-регулярным графом Рамануджана. ^[4] ${\displaystyle 3,1,1,1,1,1,-2,-2,-2,-2}$
• Граф Пейли порядка является -регулярным, и все остальные собственные значения равны , что делает графы Пейли бесконечным семейством графов Рамануджана. ${\displaystyle q}$ ${\displaystyle {\frac {q-1}{2}}}$ ${\displaystyle {\frac {-1\pm {\sqrt {q}}}{2}}}$
• В более общем случае пусть будет полиномом степени 2 или 3 над . Пусть будет образом как мультимножества, и предположим . Тогда граф Кэли для с генераторами из является графом Рамануджана. ${\displaystyle f(x)}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle S=\{f(x)\,:\,x\in \mathbb {F} _{q}\}}$ ${\displaystyle f(x)}$ ${\displaystyle S=-S}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle S}$

Математики часто интересуются построением бесконечных семейств -регулярных графов Рамануджана для каждого фиксированного . Такие семейства полезны в приложениях. ${\displaystyle d}$ ${\displaystyle d}$

Алгебраические конструкции

Несколько явных конструкций графов Рамануджана возникают как графы Кэли и являются алгебраическими по своей природе. См. обзор Винни Ли по гипотезе Рамануджана и другим аспектам теории чисел, относящимся к этим результатам. ^[5]

Любоцкий , Филлипс и Сарнак ^[2] и независимо Маргулис ^[6] показали, как построить бесконечное семейство -регулярных графов Рамануджана, когда - простое число и . Оба доказательства используют гипотезу Рамануджана , которая привела к названию графов Рамануджана. Помимо того, что они являются графами Рамануджана, эти конструкции удовлетворяют некоторым другим свойствам, например, их обхват равен , где - число узлов. ${\displaystyle (p+1)}$ ${\displaystyle p}$ ${\displaystyle p\equiv 1{\pmod {4}}}$ ${\displaystyle \Omega (\log _{p}(n))}$ ${\displaystyle n}$

Давайте набросаем конструкцию Любоцкого-Филлипса-Сарнака. Пусть будет простым числом, не равным . По теореме Якоби о четырех квадратах существуют решения уравнения , где нечетно, а четны. Каждому такому решению сопоставим матрицу Если не является квадратичным вычетом по модулю , то пусть будет графом Кэли для с этими образующими, а в противном случае пусть будет графом Кэли для с теми же образующими. Тогда является -регулярным графом на или вершинах в зависимости от того, является ли квадратичным вычетом по модулю . Доказано, что является графом Рамануджана. ${\displaystyle q\equiv 1{\bmod {4}}}$ ${\displaystyle p}$ ${\displaystyle p+1}$ ${\displaystyle p=a_{0}^{2}+a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}$ ${\displaystyle a_{0}>0}$ ${\displaystyle a_{1},a_{2},a_{3}}$ ${\displaystyle \operatorname {PGL} (2,\mathbb {Z} /q\mathbb {Z} )}$ $${\displaystyle {\tilde {\alpha }}={\begin{pmatrix}a_{0}+ia_{1}&a_{2}+ia_{3}\\-a_{2}+ia_{3}&a_{0}-ia_{1}\end{pmatrix}},\qquad i{\text{ a fixed solution to }}i^{2}=-1{\bmod {q}}.}$$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle X^{p,q}}$ ${\displaystyle \operatorname {PGL} (2,\mathbb {Z} /q\mathbb {Z} )}$ ${\displaystyle p+1}$ ${\displaystyle X^{p,q}}$ ${\displaystyle \operatorname {PSL} (2,\mathbb {Z} /q\mathbb {Z} )}$ ${\displaystyle X^{p,q}}$ ${\displaystyle (p+1)}$ ${\displaystyle n=q(q^{2}-1)}$ ${\displaystyle q(q^{2}-1)/2}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle X^{p,q}}$

Моргенштерн ^[7] позже расширил конструкцию Любоцкого, Филлипса и Сарнака. Его расширенная конструкция справедлива всякий раз, когда является степенью простого числа . ${\displaystyle p}$

Арнольд Пайзер доказал, что суперсингулярные графы изогении являются графами Рамануджана, хотя они, как правило, имеют меньший обхват, чем графы Любоцкого, Филлипса и Сарнака. ^[8] Как и в графах Любоцкого, Филлипса и Сарнака, степени этих графов всегда являются простым числом плюс один.

Вероятностные примеры

Адам Маркус , Дэниел Шпильман и Нихил Шривастава ^[9] доказали существование бесконечного числа -регулярных двудольных графов Рамануджана для любого . Позже ^[10] они доказали, что существуют двудольные графы Рамануджана любой степени и с любым числом вершин. Майкл Б. Коэн ^[11] показал, как построить эти графы за полиномиальное время. ${\displaystyle d}$ ${\displaystyle d\geq 3}$

Первоначальная работа следовала подходу Билу и Линиала . Они рассмотрели операцию, называемую 2-подъемом, которая берет -регулярный граф с вершинами и знаком на каждом ребре и создает новый -регулярный граф на вершинах. Билу и Линиал предположили, что всегда существует знак, так что каждое новое собственное значение имеет величину не более . Эта гипотеза гарантирует существование графов Рамануджана со степенью и вершинами для любого — просто начните с полного графа и итеративно берите 2-подъемы, которые сохраняют свойство Рамануджана. ${\displaystyle d}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle G'}$ ${\displaystyle 2n}$ ${\displaystyle G'}$ ${\displaystyle 2{\sqrt {d-1}}}$ ${\displaystyle d}$ ${\displaystyle 2^{k}(d+1)}$ ${\displaystyle k}$ ${\displaystyle K_{d+1}}$

Используя метод переплетения многочленов, Маркус, Шпильман и Шривастава ^[9] доказали, что гипотеза Билу и Линиала верна, когда уже является двудольным графом Рамануджана, что достаточно для вывода о существовании. Продолжение ^[10] доказало более сильное утверждение, что сумма случайных двудольных паросочетаний является графом Рамануджана с ненулевой вероятностью. Холл, Пудер и Савин ^[12] расширили оригинальную работу Маркуса, Шпильмана и Шриваставы до r -лифтов. ${\displaystyle G}$ ${\displaystyle d}$

До сих пор остается открытым вопрос о том, существует ли бесконечно много -регулярных (недвудольных) графов Рамануджана для любого . В частности, проблема открыта для , наименьший случай для которого не является степенью простого числа и, следовательно, не охватывается конструкцией Моргенштерна. ${\displaystyle d}$ ${\displaystyle d\geq 3}$ ${\displaystyle d=7}$ ${\displaystyle d-1}$

Графы Рамануджана как графы-расширители

Константа в определении графов Рамануджана асимптотически точна. Точнее, граница Алона-Боппаны утверждает, что для любого и существует такое, что все -регулярные графы с по крайней мере вершинами удовлетворяют . Это означает, что графы Рамануджана по сути являются наилучшими возможными графами-расширителями . ${\displaystyle 2{\sqrt {d-1}}}$ ${\displaystyle d}$ ${\displaystyle \epsilon >0}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \lambda (G)>2{\sqrt {d-1}}-\epsilon }$

Благодаря достижению жесткой границы на , лемма перемешивания экспандера дает отличные оценки равномерности распределения ребер в графах Рамануджана, и любые случайные блуждания на графах имеют логарифмическое время перемешивания (по числу вершин): другими словами, случайное блуждание сходится к (равномерному) стационарному распределению очень быстро. Поэтому диаметр графов Рамануджана также ограничен логарифмически по числу вершин. ${\displaystyle \lambda (G)}$

Случайные графики

Подтверждая гипотезу Алона , Фридман ^[13] показал, что многие семейства случайных графов являются слабо-рамануджановскими . Это означает, что для любого и и для достаточно большого случайный -регулярный -вершинный граф удовлетворяет с высокой вероятностью. Хотя этот результат показывает, что случайные графы близки к рамануджановским, его нельзя использовать для доказательства существования рамануджановских графов. Однако предполагается ^[14] , что случайные графы являются рамануджановскими с существенной вероятностью (примерно 52%). В дополнение к прямым числовым доказательствам, есть некоторая теоретическая поддержка этой гипотезы: спектральный зазор -регулярного графа, по-видимому, ведет себя в соответствии с распределением Трейси-Уидома из теории случайных матриц, которое предсказывает ту же асимптотику. ${\displaystyle d}$ ${\displaystyle \epsilon >0}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle \lambda (G)<2{\sqrt {d-1}}+\epsilon }$ ${\displaystyle d}$

Приложения графов Рамануджана

Графы-расширители имеют множество приложений в информатике, теории чисел и теории групп, см., например, обзор Любоцкого о приложениях к чистой и прикладной математике и обзор Хури, Линиала и Вигдерсона, который фокусируется на информатике. Графы Рамануджана в некотором смысле являются лучшими расширителями, и поэтому они особенно полезны в приложениях, где требуются расширители. Важно, что графы Любоцкого, Филлипса и Сарнака можно очень быстро обойти на практике, поэтому они практичны для приложений.

Некоторые примеры приложений включают в себя:

• В приложении к быстрым решателям для линейных систем Лапласа Ли, Пэн и Спилман ^[15] полагались на существование двудольных графов Рамануджана каждой степени, чтобы быстро аппроксимировать полный граф.
• Любецки и Перес доказали, что простое случайное блуждание демонстрирует явление обрезания на всех графах Рамануджана. ^[16] Это означает, что случайное блуждание претерпевает фазовый переход от полностью несмешанного к полностью смешанному в общей норме вариации. Этот результат в значительной степени зависит от того, что граф является графом Рамануджана, а не просто расширителем — некоторые хорошие расширители, как известно, не демонстрируют обрезания. ^[17]
• Графы Рамануджана Пайзера были предложены в качестве основы для постквантовой криптографии на основе эллиптических кривых . ^[18]
• Графы Рамануджана можно использовать для построения расширительных кодов , которые являются хорошими кодами для исправления ошибок .

Смотрите также

• Расширяющий график
• Алон-Боппана связан
• Лемма о перемешивании экспандера
• Теория спектральных графов

Ссылки

1. Обзорная статья М. Рама Мурти
2. Александр Любоцкий; Ральф Филлипс; Питер Сарнак (1988). «Графы Рамануджана». Combinatorica . 8 (3): 261–277. doi :10.1007/BF02126799. S2CID  206812625.
3. Террас, Одри (2011), Дзета-функции графиков: прогулка по саду , Cambridge Studies in Advanced Mathematics, т. 128, Cambridge University Press, ISBN 978-0-521-11367-0, г-н  2768284
4. Weisstein, Eric W. "Icosahedral Graph". mathworld.wolfram.com . Получено 29.11.2019 .
5. Ли, Винни (2020). «Гипотеза Рамануджана и ее приложения». Philosophical Transactions of the Royal Society A. 378–2163 (2163). Bibcode : 2020RSPTA.37880441W. doi : 10.1098/rsta.2018.0441. PMC 6939229. PMID  31813366 . 
6. Маргулис, Г. А. (1988). «Явные теоретико-групповые конструкции комбинаторных схем и их применение в построении экспандеров и концентраторов». Проблемы передачи информации . 24–1 : 51–60.
7. Моше Моргенштерн (1994). «Существование и явные конструкции q+1 регулярных графов Рамануджана для каждой простой степени q». Журнал комбинаторной теории . Серия B. 62 : 44–62. doi : 10.1006/jctb.1994.1054 .
8. Пайзер, Арнольд К. (1990), «Графы Рамануджана и операторы Гекке», Бюллетень Американского математического общества , Новая серия, 23 (1): 127–137, doi : 10.1090/S0273-0979-1990-15918-X , MR  1027904
9. Адам Маркус ; Дэниел Шпильман ; Нихил Шривастава (2013). Переплетение семейств I: Двудольные графы Рамануджана всех степеней (PDF) . Основы компьютерной науки (FOCS), 54-й ежегодный симпозиум IEEE 2013.
10. Адам Маркус ; Дэниел Шпильман ; Нихил Шривастава (2015). Переплетение семейств IV: Двудольные графы Рамануджана всех размеров (PDF) . Основы компьютерной науки (FOCS), 56-й ежегодный симпозиум IEEE 2015 года.
11. Майкл Б. Коэн (2016). Графы Рамануджана за полиномиальное время . Основы компьютерной науки (FOCS), 57-й ежегодный симпозиум IEEE 2016 года. arXiv : 1604.03544 . doi : 10.1109/FOCS.2016.37.
12. Холл, Крис; Пудер, Дорон; Савин, Уильям Ф. (2018). «Покрытия Рамануджана графов». Успехи математики . 323 : 367–410. arXiv : 1506.02335 . doi : 10.1016/j.aim.2017.10.042.
13. Фридман, Джоэл (2003). «Относительные экспандеры или слабо относительно графы Рамануджана». Duke Mathematical Journal . 118 (1): 19–35. doi :10.1215/S0012-7094-03-11812-8. MR  1978881.
14. Миллер, Стивен Дж.; Новикофф, Тим; Сабелли, Энтони (2008). «Распределение наибольших нетривиальных собственных значений в семействах случайных регулярных графов». Experimental Mathematics . 17 (2): 231–244. arXiv : math/0611649 . doi :10.1080/10586458.2008.10129029.
15. Ли, Инь Тат; Пэн, Ричард; Шпильман, Дэниел А. (13 августа 2015 г.). «Разреженные решатели Холецкого для линейных систем SDD». arXiv : 1506.08204 [cs.DS].
16. Любецки, Эяль; Перес, Юваль (2016-07-01). «Обрезка всех графов Рамануджана». Геометрический и функциональный анализ . 26 (4): 1190–1216. arXiv : 1507.04725 . doi :10.1007/s00039-016-0382-7. ISSN  1420-8970. S2CID  13803649.
17. Любецки, Эял; Слай, Аллан (2011-01-01). «Явные экспандеры с явлениями обрезания». Electronic Journal of Probability . 16 (нет). arXiv : 1003.3515 . doi : 10.1214/EJP.v16-869 . ISSN  1083-6489. S2CID  9121682.
18. Eisenträger, Kirsten ; Hallgren, Sean; Lauter, Kristin ; Morrison, Travis; Petit, Christophe (2018), «Суперсингулярные изогенные графы и кольца эндоморфизмов: редукция и решения» (PDF) , в Nielsen, Jesper Buus; Rijmen, Vincent (ред.), Advances in Cryptology – EUROCRYPT 2018: 37-я ежегодная международная конференция по теории и применению криптографических методов, Тель-Авив, Израиль, 29 апреля - 3 мая 2018 г., Труды, часть III (PDF) , Lecture Notes in Computer Science, т. 10822, Чам: Springer, стр. 329–368, номер документа : 10.1007/978-3-319-78372-7_11, ISBN. 978-3-319-78371-0, MR  3794837, S2CID  4850644

Дальнейшее чтение

• Джулиана Давидофф ; Питер Сарнак ; Ален Валетт (2003). Элементарная теория чисел, теория групп и графы Рамануджана . Тексты для студентов LMS. Том 55. Cambridge University Press . ISBN 0-521-53143-8. OCLC  50253269.
• Sunada, Toshikazu (1986). " L -функции в геометрии и некоторых приложениях". В Shiohama, Katsuhiro; Sakai, Takashi; Sunada, Toshikazu (ред.). Curvature and Topology of Riemannian Manifolds: Proceedings of the 17th International Taniguchi Symposium, passed in Katata, Japan, August 26–31, 1985. Lecture Notes in Mathematics. Vol. 1201. Berlin: Springer. pp. 266–284. doi :10.1007/BFb0075662. ISBN 978-3-540-16770-9. МР  0859591.

Внешние ссылки

• Обзорная статья М. Рама Мурти
• Обзорная статья Александра Любоцкого
• Обзорная статья, подготовленная Хури, Линиалом и Вигдерсоном