WikiDer > График Рамануджана

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

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

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

В полный график ${ displaystyle K_ {d + 1}}$ имеет спектр ${ displaystyle d, -1, -1, точки, -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 (п + 1)}$ -регулярные графы Рамануджана, когда ${ displaystyle p}$ это простое число и ${ Displaystyle п эквив 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} |$ , и поэтому ${ 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 с приблизительно 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 г (х) = (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 {case} c_ {1} g (v_ {s}) & { text {for}} v { text {на расстоянии}} leq k { text {from }} s, - c_ {2} g (v_ {t}) & { text {for}} v { text {на расстоянии}} leq k { text {from}} t, 0 & { text {в противном случае}} end {case}}}

куда ${ 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}) приблизительно 2 { sqrt {d-1}} left (1 - { frac {1} {2}} left ({ frac {2 pi} {m}} right) ^ {2} right),}

по желанию.

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

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

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

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

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

[lps88-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.

[m94-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

[mss13-7] Адам Маркус; Дэниел Спилман; Нихил Шривастава (2013). Чередование семейств I: двудольные графы Рамануджана всех степеней. Основы компьютерных наук (FOCS), 54-й ежегодный симпозиум IEEE 2013 г.

[mss15-8] Адам Маркус; Дэниел Спилман; Нихил Шривастава (2015). Чередование семейств IV: двудольные графы Рамануджана всех размеров. Основы компьютерных наук (FOCS), 56-й ежегодный симпозиум IEEE 2015 г.

[c16-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Navigation