Граница Алона – Боппаны

В теории спектральных графов граница Алона –Боппаны обеспечивает нижнюю границу второго по величине значения матрицы смежности собственного $d$ -регулярный график, ^{[ 1 ]} означает граф, в котором каждая вершина имеет степень $d$ . Причина интереса ко второму по величине собственному значению заключается в том, что наибольшее собственное значение гарантированно равно $d$ из-за $d$ -регулярность, при этом вектор, состоящий из всех единиц, является ассоциированным собственным вектором. Графы, которые близки к достижению этой границы, представляют собой графы Рамануджана , которые являются примерами наилучших графов-расширителей .

Его первооткрыватели — Нога Алон и Рави Боппана .

Формулировка теоремы

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

\lambda _{2}\geq 2{\sqrt {d-1}}-{\frac {2{\sqrt {d-1}}-1}{\lfloor m/2\rfloor }}.

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

Интуиция

Интуиция числа $2{\sqrt {d-1}}$ происходит от рассмотрения бесконечного $d$ - обычное дерево. ^{[ 2 ]} Этот граф является универсальным покрытием $d$ -регулярные графы, имеющие спектральный радиус $2{\sqrt {d-1}}.$

Насыщенность

Граф, который по существу насыщает границу Алона–Боппаны, называется графом Рамануджана . Точнее, граф Рамануджана — это $d$ -регулярный граф такой, что $|\lambda _{2}|,|\lambda _{n}|\leq 2{\sqrt {d-1}}.$

Теорема Фридмана ^{[ 3 ]} показывает, что для каждого $d$ и $\epsilon >0$ и для достаточно больших $n$ , случайный $d$ -регулярный график $G$ на $n$ вершины удовлетворяет $\max\{|\lambda _{2}|,|\lambda _{n}|\}<2{\sqrt {d-1}}+\epsilon$ с высокой вероятностью . Это означает, что случайный $n$ -вершина $d$ -регулярный граф обычно «почти Рамануджан».

Первое доказательство (немного более слабое утверждение)

Мы докажем несколько более слабое утверждение, а именно, опустив конкретность второго члена и просто утверждая $\lambda _{2}\geq 2{\sqrt {d-1}}-o(1).$ Здесь $o(1)$ Термин относится к асимптотическому поведению как $n$ растет без ограничений, пока $d$ остается фиксированным.

Пусть множество вершин будет $V.$ По теореме о мин-максе достаточно построить ненулевой вектор $z\in \mathbb {R} ^{|V|}$ такой, что $z^{\text{T}}\mathbf {1} =0$ и ${\frac {z^{\text{T}}Az}{z^{\text{T}}z}}\geq 2{\sqrt {d-1}}-o(1).$

Выберите какое-нибудь значение $r\in \mathbb {N} .$ Для каждой вершины в $V,$ определить вектор $f(v)\in \mathbb {R} ^{|V|}$ следующее. Каждый компонент будет индексироваться вершиной $u$ в графике. Для каждого $u,$ если расстояние между $u$ и $v$ является $k,$ тогда $u$ -компонент $f(v)$ является $f(v)_{u}=w_{k}=(d-1)^{-k/2}$ если $k\leq r-1$ и $0$ если $k\geq r.$ Мы утверждаем, что любой такой вектор $x=f(v)$ удовлетворяет

{\frac {x^{\text{T}}Ax}{x^{\text{T}}x}}\geq 2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right).

Чтобы доказать это, позвольте $V_{k}$ обозначаем множество всех вершин, расстояние между которыми равно точно $k$ от $v.$ Во-первых, обратите внимание, что

x^{\text{T}}x=\sum _{k=0}^{r-1}|V_{k}|w_{k}^{2}.

Во-вторых, обратите внимание, что

x^{\text{T}}Ax=\sum _{u\in V}x_{u}\sum _{u'\in N(u)}x_{u'}\geq \sum _{k=0}^{r-1}|V_{k}|w_{k}\left[w_{k-1}+(d-1)w_{k+1}\right]-(d-1)|V_{r-1}|w_{r-1}w_{r},

где последний член справа возникает из-за возможного пересчета членов в исходном выражении. Из вышесказанного следует, что

x^{\text{T}}Ax\geq 2{\sqrt {d-1}}\left(\sum _{k=0}^{r-1}|V_{k}|w_{k}^{2}-{\frac {1}{2}}|V_{r-1}|w_{r-1}^{2}\right),

что в сочетании с тем, что $|V_{k+1}|\leq (d-1)|V_{k}|$ для любого $k,$ урожайность

x^{\text{T}}Ax\geq 2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right)\sum _{k=0}^{r-1}|V_{k}|w_{k}^{2}.

Сочетание приведенных выше результатов доказывает требуемое неравенство.

Для удобства определите $(r-1)$ -шар вершины $v$ быть множеством вершин с расстоянием не более $r-1$ от $v.$ Обратите внимание, что запись $f(v)$ соответствующий вершине $u$ отличен от нуля тогда и только тогда, когда $u$ лежит в $(r-1)$ -шар из $x.$

Количество вершин на расстоянии $k$ данной вершины не более $1+d+d(d-1)+d(d-1)^{2}+\cdots +d(d-1)^{k-1}=d^{k}+1.$ Следовательно, если $n\geq d^{2r-1}+2,$ тогда существуют вершины $u,v$ хотя бы с расстояния $2r.$

Позволять $x=f(v)$ и $y=f(u).$ Отсюда следует, что $x^{\text{T}}y=0,$ потому что нет вершины, лежащей в $(r-1)$ -шарики обоих $x$ и $y.$ Это также правда, что $x^{\text{T}}Ay=0,$ потому что нет вершины в $(r-1)$ -шар из $x$ может быть смежным с вершиной в $(r-1)$ -шар из $y.$

Теперь существует некоторая константа $c$ такой, что $z=x-cy$ удовлетворяет $z^{\text{T}}\mathbf {1} =0.$ Тогда, поскольку $x^{\text{T}}y=x^{\text{T}}Ay=0,$

z^{\text{T}}Az=x^{\text{T}}Ax+c^{2}y^{\text{T}}Ay\geq 2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right)(x^{\text{T}}x+c^{2}y^{\text{T}}y)=2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right)z^{\text{T}}z.

Наконец, позволив $r$ расти без ограничений, обеспечивая при этом $n\geq d^{2r-1}+2$ (это можно сделать, разрешив $r$ растут сублогарифмически как функция $n$ ) образует ошибку $o(1)$ в $n.$

Второе доказательство (слегка измененное утверждение)

Это доказательство продемонстрирует слегка измененный результат, но оно дает лучшее представление об источнике числа. $2{\sqrt {d-1}}.$ Вместо того, чтобы показывать это $\lambda _{2}\geq 2{\sqrt {d-1}}-o(1),$ мы покажем это $\lambda =\max(|\lambda _{2}|,|\lambda _{n}|)\geq 2{\sqrt {d-1}}-o(1).$

Сначала выберите какое-нибудь значение $k\in \mathbb {N} .$ Обратите внимание, что число замкнутых маршрутов длины $2k$ является

\operatorname {tr} A^{2k}=\sum _{i=1}^{n}\lambda _{i}^{2k}\leq d^{2k}+n\lambda ^{2k}.

Однако верно также и то, что число замкнутых дорожек длиной $2k$ начиная с фиксированной вершины $v$ в $d$ -регулярный граф — это как минимум количество таких блужданий в бесконечном $d$ -регулярное дерево, так как бесконечное $d$ -Регулярное дерево можно использовать для покрытия графа. По определению каталонских чисел это число не меньше $C_{k}(d-1)^{k},$ где $C_{k}={\frac {1}{k+1}}{\binom {2k}{k}}$ это $k^{\text{th}}$ Каталонский номер.

Отсюда следует, что

\operatorname {tr} A^{2k}\geq n{\frac {1}{k+1}}{\binom {2k}{k}}(d-1)^{k}

\implies \lambda ^{2k}\geq {\frac {1}{k+1}}{\binom {2k}{k}}(d-1)^{k}-{\frac {d^{2k}}{n}}.

Сдача в аренду $n$ расти без ограничений и позволяя $k$ растут неограниченно, но сублогарифмически по $n$ урожайность $\lambda \geq 2{\sqrt {d-1}}-o(1).$

Ссылки

^ Нилли, А. (1991), «О втором собственном значении графа», Discrete Mathematics , 91 (2): 207–210, doi : 10.1016/0012-365X(91)90112-F , MR 1124768
^ Хори, С.; Линиал, Н.; Вигдерсон, А. (2006), «Расширяющие графы и их приложения» (PDF) , Bull. амер. Математика. Соц. (NS) , 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8
^ Фридман, Джоэл (2003). «Относительные расширители или слабо относительно графы Рамануджана». Герцог Мат. Дж . 118 (1): 19–35. дои : 10.1215/S0012-7094-03-11812-8 . МР 1978881 .

[1] Нилли, А. (1991), «О втором собственном значении графа», Discrete Mathematics , 91 (2): 207–210, doi : 10.1016/0012-365X(91)90112-F , MR 1124768

[2] Хори, С.; Линиал, Н.; Вигдерсон, А. (2006), «Расширяющие графы и их приложения» (PDF) , Bull. амер. Математика. Соц. (NS) , 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8

[3] Фридман, Джоэл (2003). «Относительные расширители или слабо относительно графы Рамануджана». Герцог Мат. Дж . 118 (1): 19–35. дои : 10.1215/S0012-7094-03-11812-8 . МР 1978881 .

[ 1 ]

[ 2 ]

[ 3 ]