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

07.10.2021

В спектральной теории графов граф Рамануджана, названный по имени индийского математика Рамануджана, — это регулярный граф, спектральная щель которого почти настолько велика, насколько это возможно (см. статью «Экстремальная теория графов»). Такие графы являются прекрасными спектральными экспандерами.

Примерами графов Рамануджана служат клики, полные двудольные графы K n , n {displaystyle K_{n,n}} и граф Петерсена. Как замечает Мурти в обзорной статье, графы Рамануджана «сплавляют воедино различные ветви чистой математики, а именно, теорию чисел, теорию представлений и алгебраическую геометрию». Как заметил Тосикадзу Сунада, регулярный граф является графом Рамануджана тогда и только тогда, когда его дзета-функция Ихары удовлетворяет аналогу гипотезы Римана.

Определение

Пусть G {displaystyle G} будет связным d {displaystyle d} -регулярным графом с n {displaystyle n} вершинами и пусть λ 0 ⩾ λ 1 ⩾ ⋯ ⩾ λ n − 1 {displaystyle lambda _{0}geqslant lambda _{1}geqslant cdots geqslant lambda _{n-1}} будут собственными числами матрицы смежности графа G {displaystyle G} . Поскольку граф G {displaystyle G} связен и d {displaystyle d} -регулярен, его собственные числа удовлетворяют неравенствам d = λ 0 > λ 1 ⩾ ⋯ ⩾ λ n − 1 ⩾ − d {displaystyle d=lambda _{0}>lambda _{1}geqslant cdots geqslant lambda _{n-1}geqslant -d} . Если существует значение λ i {displaystyle lambda _{i}} , для которого | λ i | < d {displaystyle |lambda _{i}|<d} , определим

λ ( G ) = max | λ i | < d | λ i | . {displaystyle lambda (G)=max _{|lambda _{i}|<d}|lambda _{i}|.,}

d {displaystyle d} -Регулярный граф G {displaystyle G} является графом Рамануджана, если λ ( G ) ⩽ 2 d − 1 {displaystyle lambda (G)leqslant 2{sqrt {d-1}}} .

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

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

Для фиксированного значения d {displaystyle d} и большого n {displaystyle n} d {displaystyle d} -регулярные графы Рамануджана с n {displaystyle n} вершинами почти минимизируют λ ( G ) {displaystyle lambda (G)} . Если G {displaystyle G} является d {displaystyle d} -регулярным графом с диаметром m {displaystyle m} , теорема Алона утверждает

λ 1 ⩾ 2 d − 1 − 2 d − 1 − 1 ⌊ m / 2 ⌋ . {displaystyle lambda _{1}geqslant 2{sqrt {d-1}}-{frac {2{sqrt {d-1}}-1}{lfloor m/2 floor }}.}

Если G {displaystyle G} является d {displaystyle d} -регулярным и связным по меньшей мере на трёх вершинах, | λ 1 | < d {displaystyle |lambda _{1}|<d} , а потому λ ( G ) ⩾ λ 1 {displaystyle lambda (G)geqslant lambda _{1}} . Пусть G n d {displaystyle {mathcal {G}}_{n}^{d}} будет множеством всех связных d {displaystyle d} -регулярных графов G {displaystyle G} по меньшей мере с n {displaystyle n} вершинами. Поскольку минимальный диаметр графа в G n d {displaystyle {mathcal {G}}_{n}^{d}} стремится к бесконечности при фиксированном d {displaystyle d} и увеличивающемся n {displaystyle n} , из этой теоремы следует теорема Алона и Боппана, которая утверждает

lim n → ∞ inf G ∈ G n d λ ( G ) ⩾ 2 d − 1 . {displaystyle lim _{n o infty }inf _{Gin {mathcal {G}}_{n}^{d}}lambda (G)geqslant 2{sqrt {d-1}}.}

Чуть более строгая граница

λ 1 ⩾ 2 d − 1 ⋅ ( 1 − c m 2 ) , {displaystyle lambda _{1}geqslant 2{sqrt {d-1}}cdot left(1-{frac {c}{m^{2}}} ight),}

где c ≈ 2 π 2 {displaystyle capprox 2pi ^{2}} . Набросок доказательства Фридмана следующий. Возьмём k = ⌊ m 2 ⌋ − 1 {displaystyle k=leftlfloor {frac {m}{2}} ight floor -1} . Пусть T d , k {displaystyle T_{d,k}} будет d {displaystyle d} -регулярным деревом высоты k {displaystyle k} и пусть A T k {displaystyle A_{T_{k}}} будет его матрицей смежности. Мы хотим доказать, что λ ( G ) ⩾ λ ( T d , k ) = 2 d − 1 cos ⁡ θ {displaystyle lambda (G)geqslant lambda (T_{d,k})=2{sqrt {d-1}}cos heta } для некоторого θ {displaystyle heta } , зависящего только от m {displaystyle m} . Определим функцию g : V ( T d , k ) → R {displaystyle g:V(T_{d,k}) ightarrow mathbb {R} } следующим образом g ( x ) = ( d − 1 ) − δ / 2 ⋅ sin ⁡ ( ( k + 1 − δ ) θ ) {displaystyle g(x)=(d-1)^{-delta /2}cdot sin((k+1-delta ) heta )} , где δ {displaystyle delta } является расстоянием от x {displaystyle x} до корня T d , k {displaystyle T_{d,k}} . Выбирая θ {displaystyle heta } близко к 2 π / m {displaystyle 2pi /m} , можно доказать, что A t , k g = λ ( T d , k ) g {displaystyle A_{t,k}g=lambda (T_{d,k})g} . Теперь пусть s {displaystyle s} и t {displaystyle t} будут парой вершин на расстоянии m {displaystyle m} и определим

f ( v ) = { c 1 g ( v s ) d i s t ( v , s ) ⩽ k , − c 2 g ( v t ) d i s t ( v , t ) ⩽ k , 0 {displaystyle f(v)={egin{cases}c_{1}g(v_{s})&&dist(v,s)leqslant k,-c_{2}g(v_{t})&&dist(v,t)leqslant k,&end{cases}}}

где v s {displaystyle v_{s}} — вершина в T d , k {displaystyle T_{d,k}} , расстояние от которой до корня равно расстоянию от v {displaystyle v} до s {displaystyle s} ( d i s t ( v , s ) {displaystyle dist(v,s)} ) и симметрично для v t {displaystyle v_{t}} . Путём выбора подходящих c 1 , c 2 {displaystyle c_{1},c_{2}} мы получим f ⊥ 1 {displaystyle fperp 1} , ( A f ) v ⩾ λ ( T d , k ) f v {displaystyle (Af)_{v}geqslant lambda (T_{d,k})f_{v}} для v {displaystyle v} близких к s {displaystyle s} и ( A f ) v ⩽ λ ( T d , k ) f v {displaystyle (Af)_{v}leqslant lambda (T_{d,k})f_{v}} для v {displaystyle v} близких к t {displaystyle t} . Тогда по теореме о минимаксе λ ( G ) ⩾ f A f T / ‖ f ‖ 2 ⩾ λ ( T d , k ) {displaystyle lambda (G)geqslant fAf^{T}/|f|^{2}geqslant lambda (T_{d,k})} .

Построения

Построения графов Рамануджана часто алгебраические.

  • Лубоцки, Филлипс и Сарнак показали, как построить бесконечное семейство ( p + 1 ) {displaystyle (p+1)} -регулярных графов Рамануджана, когда p {displaystyle p} является простым числом и p ≡ 1 ( mod 4 ) {displaystyle pequiv 1{pmod {4}}} . Их доказательство использует гипотезу Рамануджана, откуда и получили название графы Рамануджана. Кроме свойства быть графами Рамануджана, их построение имеет ряд других свойств. Например, обхват равен Ω ( log p ⁡ ( n ) ) {displaystyle Omega (log _{p}(n))} , где n {displaystyle n} равно числу узлов.
  • Моргенштерн расширил построение Лубоцки, Филлипса и Сарнака. Его расширенное построение допустимо, если p {displaystyle p} является степенью простого числа.
  • Арнольд Пицер доказал, что суперсингулярные изогении графа являются графами Рамануджана, хотя, как правило, они имеют меньший обхват, чем графы Лубоцки, Филлипса и Сарнака. Подобно графам Лубоцки, Филлипса и Сарнака, степени этих графов всегда равны простому числу + 1. Эти графы предлагаются в качестве базиса постквантовой эллиптической криптографии.
  • Адам Маркус, Даниэль Спильман и Никхил Сривастава доказали существование d {displaystyle d} -регулярных двудольных графов Рамануджана для любого d {displaystyle d} . Позднее они доказали, что существуют двудольные графы Рамануджана любой степени и с любым числом вершин. Михаэль Б. Коэн показал, каким образом строить эти графы за полиномиальное время.


Имя:*
E-Mail:
Комментарий: