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

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

Определение [ править ]

Пусть связной -регулярный граф с вершинами, и пусть быть собственными значениями по смежности матрицы из (или спектра в ). Поскольку является связным и -регулярным, его собственные значения удовлетворяют . ${\ 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}}}$

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

Граф Петерсена имеет спектр , поэтому это 3-регулярный граф Рамануджана. Граф икосаэдра - это 5-регулярный граф Рамануджана. ^[3]${\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}}}$

Математики часто интересуются построением -регулярных графов Рамануджана для каждого фиксированного . Современные конструкции бесконечных семейств таких графов Рамануджана часто являются алгебраическими.${\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] доказали существование бесконечного числа -регулярных двудольных графов Рамануджана для любого . Позже ^[8] они доказали, что существуют двудольные графы Рамануджана любой степени и любого числа вершин. Майкл Б. Коэн ^[9] показал, как построить эти графы за полиномиальное время.${\displaystyle d}$${\displaystyle d\geq 3}$

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

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

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

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

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

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

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

Всякий раз , когда это -регулярен и подключено , по крайней мере , три вершины, и , следовательно . Позвольте быть множество всех связных -регулярных графов по крайней мере с вершинами. Поскольку минимальный диаметр графов приближается к бесконечности для фиксированных и возрастающих , из этой теоремы следует более ранняя теорема Алона и Боппаны ^[12], которая гласит:${\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}$

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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