График Рамануджана - Ramanujan graph

В спектральная теория графов, а График Рамануджана, это регулярный граф чей спектральный промежуток почти как можно больше (см. экстремальная теория графов ). Такие графики отличные спектральные расширители. В качестве Обзорная статья Мёрти отмечает, что графики Рамануджана «объединяют различные разделы чистой математики, а именно: теория чисел, теория представлений, и алгебраическая геометрия ". Эти графики косвенно названы в честь Шриниваса Рамануджан; их имя происходит от Гипотеза Рамануджана – Петерсона, который использовался при построении некоторых из этих графов.

Определение

Позволять ${\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}|,|\lambda _{n}|)}$. Связанный ${\displaystyle d}$-регулярный график ${\displaystyle G}$ это График Рамануджана если ${\displaystyle \lambda (G)\leq 2{\sqrt {d-1}}}$.

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

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

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

В полный график ${\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}$.

В Граф Петерсена имеет спектр ${\displaystyle 3,1,1,1,1,1,-2,-2,-2,-2}$, так что это 3-регулярный граф Рамануджана. В икосаэдрический график является 5-регулярным графом Рамануджана.^[3]

А Граф Пэли порядка ${\displaystyle q}$ является ${\displaystyle {\frac {q-1}{2}}}$-регулярно со всеми остальными собственными значениями ${\displaystyle {\frac {-1\pm {\sqrt {q}}}{2}}}$, что делает графы Пэли бесконечным семейством графов Рамануджана.

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

• Любоцкий, Филлипс и Сарнак^[1] показать, как построить бесконечное семейство ${\displaystyle (p+1)}$-регулярные графы Рамануджана, когда ${\displaystyle p}$ это простое число и ${\displaystyle p\equiv 1{\pmod {4}}}$. В их доказательстве используется Гипотеза Рамануджана, что и привело к названию графов Рамануджана. Помимо того, что они являются графами Рамануджана, их конструкция удовлетворяет некоторым другим свойствам, например обхват является ${\displaystyle \Omega (\log _{p}(n))}$ куда ${\displaystyle n}$ количество узлов.
• Моргенштерн^[4] расширила строительство Любоцкого, Филипса и Сарнака. Его расширенная конструкция верна всякий раз, когда ${\displaystyle p}$ это основная сила.
• Арнольд Пайзер доказал, что суперсингулярные графы изогении являются Рамануджаном, хотя, как правило, имеют меньший обхват, чем графики Любоцкого, Филлипса и Сарнака.^[5] Подобно графам Любоцкого, Филлипса и Сарнака, степени этих графов всегда равны простому числу плюс один. Эти графики были предложены в качестве основы для постквантовый криптография с эллиптической кривой.^[6]
• Адам Маркус, Дэниел Спилман и Нихил Шривастава^[7] доказал существование бесконечно многих ${\displaystyle d}$-обычный двудольный Графы Рамануджана для любых ${\displaystyle d\geq 3}$. Потом^[8] они доказали, что существуют двудольные графы Рамануджана любой степени и любого числа вершин. Майкл Б. Коэн^[9] показал, как построить эти графы за полиномиальное время.

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

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

Постоянная ${\displaystyle 2{\sqrt {d-1}}}$ в определении графов Рамануджана - наилучшая возможная константа для каждого ${\displaystyle d}$ а для больших графиков: другими словами, для каждого ${\displaystyle d}$ и ${\displaystyle \epsilon >0}$, Существует ${\displaystyle n}$ так что все ${\displaystyle d}$-регулярные графики ${\displaystyle G}$ по крайней мере с ${\displaystyle n}$ вершины удовлетворяют ${\displaystyle \lambda (G)>2{\sqrt {d-1}}-\epsilon }$. (См. Ниже более точные утверждения и наброски доказательств.) С другой стороны, Фридман^[10] показал, что для каждого ${\displaystyle d}$ и ${\displaystyle \epsilon >0}$ и для достаточно больших ${\displaystyle n}$, случайный ${\displaystyle d}$-обычный ${\displaystyle n}$-вершинный граф ${\displaystyle G}$ удовлетворяет ${\displaystyle \lambda (G)<2{\sqrt {d-1}}+\epsilon }$ с большой вероятностью. Это означает, что графики Рамануджана по сути являются наилучшими из возможных. графики расширения.

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

Экстремальность графов Рамануджана

Если ${\displaystyle G}$ это ${\displaystyle d}$-регулярный граф с диаметр ${\displaystyle m}$, а Теорема Нога Алон^[11] состояния

${\displaystyle \lambda _{2}(G)\geq 2{\sqrt {d-1}}-{\frac {2{\sqrt {d-1}}-1}{\lfloor m/2\rfloor }}.}$

В любое время ${\displaystyle G}$ является ${\displaystyle d}$-регулярны и связаны не менее чем на трех вершинах, ${\displaystyle |\lambda _{2}|<d}$, и поэтому ${\displaystyle \lambda (G)\geq \lambda _{2}}$. Позволять ${\displaystyle {\mathcal {G}}_{n}^{d}}$ быть набором всех связанных ${\displaystyle d}$-регулярные графики ${\displaystyle G}$ по крайней мере с ${\displaystyle n}$ вершины. Поскольку минимальный диаметр графов в ${\displaystyle {\mathcal {G}}_{n}^{d}}$ приближается к бесконечности для фиксированного ${\displaystyle d}$ и увеличение ${\displaystyle n}$, из этой теоремы следует более ранняя теорема Алона и Боппаны.^[12] в котором говорится

${\displaystyle \lim _{n\to \infty }\inf _{G\in {\mathcal {G}}_{n}^{d}}\lambda (G)\geq 2{\sqrt {d-1}}.}$

Несколько более сильная оценка

${\displaystyle \lambda _{2}(G)\geq 2{\sqrt {d-1}}\cdot \left(1-{\frac {c}{m^{2}}}\right),}$

куда ${\displaystyle c\approx 2\pi ^{2}}$. Схема доказательства следующая. Брать ${\displaystyle k=\left\lfloor {\frac {m}{2}}\right\rfloor -1}$. Позволять ${\displaystyle T_{d,k}}$ быть полным ${\displaystyle (d-1)}$-арное дерево высоты ${\displaystyle k}$ (каждая внутренняя вершина имеет ${\displaystyle d-1}$ дети), и пусть ${\displaystyle A_{d,k}}$ - его матрица смежности. Мы хотим доказать, что ${\displaystyle \lambda _{2}(G)\geq \lambda _{1}(T_{d,k})=2{\sqrt {d-1}}\cos \theta }$, куда ${\displaystyle \theta ={\frac {\pi }{k+2}}}$. Определите функцию ${\displaystyle g:V(T_{d,k})\rightarrow \mathbb {R} }$ к ${\displaystyle g(x)=(d-1)^{-\delta /2}\cdot \sin((k+1-\delta )\theta )}$, куда ${\displaystyle \delta }$ это расстояние от ${\displaystyle x}$ к корню ${\displaystyle T_{d,k}}$. Можно убедиться, что ${\displaystyle A_{t,k}g=\lambda _{1}(T_{d,k})g}$ и это ${\displaystyle \lambda _{1}(T_{d,k})}$ действительно является наибольшим собственным значением ${\displaystyle A_{d,k}}$. Теперь позвольте ${\displaystyle s}$ и ${\displaystyle t}$ пара вершин на расстоянии ${\displaystyle m}$ в ${\displaystyle G}$ и определить

${\displaystyle f(v)={\begin{cases}c_{1}g(v_{s})&{\text{for }}v{\text{ at distance }}\leq k{\text{ from }}s,\\-c_{2}g(v_{t})&{\text{for }}v{\text{ at distance }}\leq k{\text{ from }}t,\\0&{\text{otherwise,}}\end{cases}}}$

куда ${\displaystyle v_{s}}$ является вершиной в ${\displaystyle T_{d,k}}$ расстояние до корня которого равно расстоянию от ${\displaystyle v}$ к ${\displaystyle s}$ и симметричный для ${\displaystyle v_{t}}$. (Можно думать об этом как о «вложении» двух непересекающихся копий ${\displaystyle T_{d,k}}$, с некоторыми вершинами, свернувшимися в одну.) Выбирая значение положительных вещественных чисел ${\displaystyle c_{1},c_{2}}$ правильно мы получаем ${\displaystyle f\perp 1}$, ${\displaystyle (Af)_{v}\geq \lambda _{1}(T_{d,k})f_{v}}$ за ${\displaystyle v}$ рядом с ${\displaystyle s}$ и ${\displaystyle (Af)_{v}\leq \lambda _{1}(T_{d,k})f_{v}}$ за ${\displaystyle v}$ рядом с ${\displaystyle t}$. Затем по теорема мин-макс мы получили

$${\displaystyle \lambda _{2}(G)\geq fAf^{T}/\|f\|^{2}\geq \lambda _{1}(T_{d,k})\approx 2{\sqrt {d-1}}\left(1-{\frac {1}{2}}\left({\frac {2\pi }{m}}\right)^{2}\right),}$$

по желанию.

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

• График расширителя
• Лемма о перемешивании расширителей
• Теория спектральных графов

Рекомендации

1. Александр Любоцкий; Ральф Филлипс; Питер Сарнак (1988). «Графы Рамануджана». Комбинаторика. 8 (3): 261–277. Дои:10.1007 / BF02126799.
2. Террас, Одри (2011), Дзета-функции графиков: прогулка по саду, Кембриджские исследования по высшей математике, 128, Издательство Кембриджского университета, ISBN  978-0-521-11367-0, МИСТЕР  2768284
3. Вайсштейн, Эрик В. «Икосаэдрический график». mathworld.wolfram.com. Получено 2019-11-29.
4. Моше Моргенштерн (1994). «Существование и явные конструкции q + 1 регулярных графов Рамануджана для каждой простой степени q». Журнал комбинаторной теории, серия B. 62: 44–62. Дои:10.1006 / jctb.1994.1054.
5. Пайзер, Арнольд К. (1990), "Графы Рамануджана и операторы Гекке", Бюллетень Американского математического общества, Новая серия, 23 (1): 127–137, Дои:10.1090 / S0273-0979-1990-15918-X, МИСТЕР  1027904
6. Эйзентрегер, Кирстен; Халлгрен, Шон; Лаутер, Кристин; Моррисон, Трэвис; Пети, Кристоф (2018), «Суперсингулярные графы изогений и кольца эндоморфизмов: редукции и решения» (PDF)в Нильсене - Джеспер Буус; Раймен, Винсент (ред.), Достижения в криптологии - EUROCRYPT 2018: 37-я ежегодная международная конференция по теории и применению криптографических методов, Тель-Авив, Израиль, 29 апреля - 3 мая 2018 г., Материалы, часть III (PDF), Конспект лекций по информатике, 10822, Cham: Springer, стр. 329–368, Дои:10.1007/978-3-319-78372-7_11, МИСТЕР  3794837
7. Адам Маркус; Дэниел Спилман; Нихил Шривастава (2013). Чередование семейств I: двудольные графы Рамануджана всех степеней. Основы компьютерных наук (FOCS), 54-й ежегодный симпозиум IEEE 2013 г.
8. Адам Маркус; Дэниел Спилман; Нихил Шривастава (2015). Чередование семейств IV: двудольные графы Рамануджана всех размеров. Основы компьютерных наук (FOCS), 56-й ежегодный симпозиум IEEE 2015 г.
9. Майкл Б. Коэн (2016). Графы Рамануджана за полиномиальное время. Основы компьютерных наук (FOCS), 57-й ежегодный симпозиум IEEE 2016 г. arXiv:1604.03544. Дои:10.1109 / FOCS.2016.37.
10. Фридман, Джоэл (2003). «Относительные расширители или слабо относительно графы Рамануджана». Duke Math. J. 118 (1): 19–35. Дои:10.1215 / S0012-7094-03-11812-8. МИСТЕР  1978881.
11. Нилли, А. (1991), «О втором собственном значении графа», Дискретная математика, 91 (2): 207–210, Дои:10.1016 / 0012-365X (91) 90112-F, МИСТЕР  1124768.
12. Алон, Н. (1986). «Собственные значения и расширители». Комбинаторика. 6 (2): 83–96. Дои:10.1007 / BF02579166. МИСТЕР  0875835.

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

• Гилиана Давыдова; Питер Сарнак; Ален Валетт (2003). Элементарная теория чисел, теория групп и графы Раманджуана. Студенческие тексты LMS. 55. Издательство Кембриджского университета. ISBN  0-521-53143-8. OCLC  50253269.
• Т. Сунада (1985). «L-функции в геометрии и некоторых приложениях». Конспект лекций по математике. Конспект лекций по математике. 1201: 266–284. Дои:10.1007 / BFb0075662. ISBN  978-3-540-16770-9.

внешняя ссылка

• Обзорный доклад М. Рама Мурти