Граница Алон – Боппана - Alon–Boppana bound

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

Утверждение теоремы

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

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

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

Интуиция

В Граф Кэли из свободная группа на двух генераторах ${\displaystyle a}$ и ${\displaystyle b}$ пример бесконечного ${\displaystyle d}$-регулярное дерево для ${\displaystyle d=4.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}^{2}\right),}$

что в сочетании с тем фактом, что ${\displaystyle |V_{k+1}|\leq (d-1)|V_{k}|}$ для любого ${\displaystyle k,}$ дает

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

Комбинация приведенных выше результатов доказывает желаемое неравенство.

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

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

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

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

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

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

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

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

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

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

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

Следует, что

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

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

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

Рекомендации

1. Нилли, А. (1991), «О втором собственном значении графа», Дискретная математика, 91 (2): 207–210, Дои:10.1016 / 0012-365X (91) 90112-F, МИСТЕР  1124768
2. Hoory, S .; Linial, N .; Вигдерсон, А. (2006), «Графы-расширители и их приложения» (PDF), Бык. Амер. Математика. Soc. (Н.С.), 43 (4): 439–561, Дои:10.1090 / S0273-0979-06-01126-8
3. Фридман, Джоэл (2003). «Относительные расширители или слабо относительно графы Рамануджана». Duke Math. J. 118 (1): 19–35. Дои:10.1215 / S0012-7094-03-11812-8. МИСТЕР  1978881.