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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

Нарисуем конструкцию Любоцкого-Филлипса-Сарнака. Позволять $q\equiv 1{\bmod {4}}$ быть простым числом, не равным $p$. По теореме четырех квадратов Якоби существуют $p+1$ решения уравнения $p=a_{0}^{2}+a_{1}^{2}+a_{2}^{2}+a_{3}^{2}$ где $a_{0}>0$ это странно и $a_{1},a_{2},a_{3}$ четные. Каждому такому решению сопоставьте $\operatorname {PGL} (2,\mathbb {Z} /q\mathbb {Z} )$ матрица

$${\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}}.$$

Если $p$ не является квадратичным вычетом по модулю $q$ позволять $X^{p,q}$ быть графом Кэли $\operatorname {PGL} (2,\mathbb {Z} /q\mathbb {Z} )$ с этими $p+1$ генераторы, а иначе, пусть $X^{p,q}$ быть графом Кэли $\operatorname {PSL} (2,\mathbb {Z} /q\mathbb {Z} )$ с теми же генераторами. Затем $X^{p,q}$ это $(p+1)$-регулярный график на $n=q(q^{2}-1)$ или $q(q^{2}-1)/2$ вершины в зависимости от того, есть или нет $p$ является квадратичным вычетом по модулю $q$. Доказано, что $X^{p,q}$ является графом Рамануджана.

Моргенштерн позже расширили строительство Любоцкого, Филлипса и Сарнака. Его расширенная конструкция сохраняется всякий раз, когда $p$ это высшая сила .

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

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

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

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

Использование метода переплетения полиномов Маркуса, Спилмана и Шриваставы. доказал, что гипотеза Билу и Линиала верна, когда $G$ уже является двудольным графом Рамануджана, чего достаточно, чтобы сделать вывод о существовании. Продолжение доказал более сильное утверждение о том, что сумма $d$ случайные двудольные паросочетания являются Рамануджаном с ненулевой вероятностью. Холл, Пудер и Савин распространил первоначальную работу Маркуса, Спилмана и Шриваставы на r -лифтинги.

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

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

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

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

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

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

графов

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

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

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

См. также

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

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

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

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

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