알론-보파나 바운드

스펙트럼 그래프 이론에서 알론-보파나 바운드는 $d{\displaystyle }$ ${\displaystyle d}$ - 정규$$ 그래프의 인접 행렬 중 두 번째로 큰 고유값에서 하한을 제공하며,^[1] 이는 모든 꼭지점에 도 $d{\displaystyle }${\$displaystyle d}$이(가) 있는 그래프를 의미한다$.$두 번째로 큰 고유값에 관심을 갖는 이유는 $d{\displaystyle }$ ${\displaystyle d}$ -정규성으로$$ 인해$$ 가장 큰 $고유값$이 d ${\displaystyle d}$이(가) 보장되며, 모든 원 벡터는 관련 고유 벡터가 되기 때문이다.이 한계를 충족하는 데 가까운 그래프는 Ramanujan 그래프인데, 이는 가능한 한 가장 좋은 확장자 그래프의 예들이다.

그것의 발견자는 노가 알론과 라비 보파나이다.

정리명세서

$G{\displaystyle }$ ${\$$displaystyle G}$을(를) $직경{\displaystyle }$ m ${\displaystyle m$의 $정점$에$$대한 d {\$displaystyle$ $d}$ - 정규$$ 그래프로$$ 하고 A {\$displaystyle A}$을(를$)$ 인접 행렬로 한다$$.$\lambda {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$2 n${\displaystyle }$n n ${\displaystyle n_{}}$ n ${\$을 고유값으로 한다$$.그러면

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

위의 진술은 노가 알론에 의해 증명된 원본이다.약간 약한 변종들은 증거의 용이성을 향상시키거나 직관을 향상시키기 위해 존재한다.이 중 두 가지는 아래의 교정에서 볼 수 있다.

직감

숫자 $2{\displaystyle \mathrm{}}$ ${\displaystyle \sqrt{\mathrm{d}}}$ -${\displaystyle \sqrt{}}$1 ${\$ 2${\sqrt{d-1}$의 직관은 무한 $d{\displaystyle }$ ${\displaystyle d}$ - 정규$$ 트리를 고려하는 데서 비롯된다$$.^[2]이 그래프는 $d{\displaystyle }$ ${\displaystyle d}$ - 일반$$ 그래프의 범용 표지로, 스펙트럼 반지름 2 ${\displaystyle d\sqrt{}}$ -${\displaystyle \sqrt{1}}$. ${\displaystyle 2{\sqrt {d-1}$을(를) 가지고 있다.$}$

포화

알론-보파나 결합을 본질적으로 포화시킨 그래프를 라마누잔 그래프라고 한다.보다 정확히 말하면, Ramanujan 그래프는 d ${\\displaystyle d}$ - $정규$ 그래프로서, ${\displaystyle \lambda {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle {}_{}{\lambda }_{}}$ n ${\displaystyle \le {}_{}}$ ${\displaystyle 2\sqrt{}}$ ${\displaystyle \sqrt{\mathrm{d}}}$- 1${\displaystyle }$. ${\displaysty \lambda _{2$},$\lambda _{n} \leq$ 2${\sqrt {d-1}.$$}$

Friedman[3]에 의한 정리 모든 d{\displaystyle d}과ϵ>0{\displaystyle \epsilon>0}과 충분히 큰 n{n\displaystyle}, 무작위 d은,{\displaystyle d}n{n\displaystyle}vertices에-regular 그래프 G{G\displaystyle}가 정도이다{λ 2, λ n.을 보여 주 }<> -+ ${\displaystyle \max\{\ \da _{2$},$\lambda _{n}$\}<$2{\sqrt{d-1}+\엡실론$} 높은 확률로.즉, 임의의 $n{\displaystyle }$ ${\displaystyle n}$ -vertex$$ $d{\displaystyle }$ ${\displaystyle d}$ -정규$$ 그래프가 일반적으로 "거의 라마누잔"이라는 뜻이다.

첫 번째 증거(약하게 약한 진술)

우리는 좀 더 약한 진술 즉, 연임에서 특수성을 떨어뜨리고 단순히 ${\displaystyle {\lambda \mathrm{}}_{}}$ 2 ${\displaystyle {}_{}}$ ${\displaystyle 2\sqrt{}}$d - ${\displaystyle 1}$ -${\displaystyle }$o (${\displaystyle 1}$ )${\displaystyle }$. ${\displaystyle \lambda _{2}\geq$ 2${\sqrt{d-1-o(1)$를 주장할 것이다$.$$}$ 여기서$$ $o{\displaystyle }$( ${\displaystyle 1}$) ${\displaystyle o(1)}$ 용어는$$ $n{\displaystyle }$ ${\displaystyle$ $n$$}$이(가) 구속 없이 성장하는 반면$$ $d{\displaystyle }$ ${\displaystyle$ d}은(가$)$ 고정되어 있기$$ 때문에 점증하지 않는 행동을 말한다.

정점 $세트$를 V${\displaystyle .}${\$displaystyle$ V$.}$최소-최대 정리를$$ 통해 0이 아닌 벡터 $z{\displaystyle }$vector ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle V^{}}$ $displaystyle$ z$\in \mathb {R$$}^{{V$$}}}}}$과 같은 ${\displaystyle {비제로}^{}}$ 벡터 $z$를 구성하면 ${\displaystyle \mathrm{충분}}$하다$.$$T}\mathbf$ {1}$=0}$ 및$$ z $T{\displaystyle \frac{{}^{}}{}}$ ${\displaystyle \frac{A^{}}{}}$ z ${\displaystyle \frac{z}{}\frac{{}^{}}{}}$ ${\displaystyle 2}$ ${\displaystyle d\sqrt{}}$- ${\displaystyle \sqrt{1}}$ -${\displaystyle o}$( ${\displaystyle 1}$)${\displaystyle }$. ${\displaystyle {\frac$ {$z^{\text{\$text{}$T}}아즈}{z^{\text{$$T}}}}\geq 2{\$$sqrt {{d-1-o(1)$$}$

${\displaystyle 일부\mathbb{}}$ 값 $r{\displaystyle }$ ${\displaystyle \in }$ N${\displaystyle }$. ${\displaystyle r\in$$$$\$$mathb$ ${N}}$$V$의 각 꼭지점에 대해$$ 다음과 같이$$ ${\displaystyle {\mathbb{}}^{}}$ $f{\displaystyle }$(${\displaystyle v}$ ${\displaystyle ){}^{}}$verte R V {\$displaystyle f(v)\in \mathb {R} ^{$ V$}}$를 정의하십시오.각 구성요소는 그래프의$$ 꼭지점 $u{\displaystyle }$ ${\displaystyle u}$에 의해 색인화된다.For each ${\displaystyle u,}$ if the distance between ${\displaystyle u}$ and ${\displaystyle v}$ is ${\displaystyle k,}$ then the ${\displaystyle u}$-component of ${\displaystyle f(v)}$ is ${\displaystyle f(v)_{u}=w_{k}=(d-1)^{-k/2}}$$k{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle r}$ -${\displaystyle 1}$ ${\displaystyle k\leq r-1$$}$ 및$$ $k{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle r}$. ${\displaystyle k\geq$ r$.}$인 경우$$${\displaystyle$ $x$$=f(v)}$ 이러한 벡터 $x{\displaystyle }$=${\displaystyle f}$ = f${\displaystyle (v}$)가 충족된다고$$ 주장함$$

${\displaystyle {\frac {x^{\text}T}}Ax}{x^{\text{T}}x}\geq 2{\sqrt {d-1}\좌측(1-{\prac {1}{2r}}\우측).}$

이를 증명하기 위해 V${\displaystyle }$${\displaystyle k_{}}$ ${\$에서 $정확히$ k ${\displaystyle k}$의 거리를 가진 모든 정점의 집합을 표시하도록$$ 한다. 먼저$$, 주의하십시오.

${\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}\좌(\sum _{k=0}^{r-1}V_{k}w_{k}^{2}-{\frac{1}{1}{1}{1}{2}} V_{r-1}w_{r-1}^{2}\오른쪽)}}$

즉, V ${\displaystyle k_{}}$+ ${\displaystyle 1_{}{}_{}}$\${\displaystyle }$(${\displaystyle d}$- ${\displaystyle 1}$) ${\displaystyle V{}_{}}$ ${\displaystyle k_{}}$ $displaystyle V_{k+1} \leq (d-1) V_{k} }$ }의${\displaystyle }$k$$, {\$displaystyle$k, {\displaystytle k,} 산출량$$$:}$

${\displaystyle x^{\text}T}Ax\geq 2{\sqrt{d-1}\좌측(1-{\frac {1}{2r}\우측)\sum _{k=0}^{r-1}V_{k}w_{k}^{k}^{k}^{2}.}$

위의 결과를 종합하면 원하는 불평등이 입증된다.

${\displaystyle \mathrm{편의}}$를 위해 $꼭지점{\displaystyle }$ v ${\$$displaystyle$ v$}$의 (${\displaystyle \mathrm{r}}$- 1${\displaystyle }$) ${\$$displaystyle$$v}$ -ball을$$ $v{\displaystyle .}$ ${\displaystyle v.}$에서 최대 ${\displaystyle \mathrm{r}}$- 1 ${\displaystyle r-1}$의 정점 집합으로$$ 정의하십시오. $f$ ${\displaystyle (v}$) ${\displaystylease u}$에 해당하는$$ $f(v)$ 항목이 있음$$ $u{\displaystyle }$ ${\displaystyle u$${\displaystyle \}}$이$($가${\displaystyle )}$ $x{\displaystyle }$. ${\displaystyle($r-1)$-ball$ of$$ x . ${\displaystyle x.}$에 있는$$ 경우에만 0이 아님

The number of vertices within distance ${\displaystyle k}$ of a given vertex is at most ${\displaystyle 1+d+d(d-1)+d(d-1)^{2}+\cdots +d(d-1)^{k-1}=d^{k}+1.}$ Therefore, if ${\displaystyle n\geq d^{2r-1}+2,}$ then there exist vertices $u{\displaystyle ,}$ ${\displaystyle v}$ ${\displaystyle u,v},$ 최소$$ ${\displaystyle \mathrm{2r}.}$ ${\displaystyle 2r.$$}$

$x{\displaystyle }$= ${\displaystyle f}$(${\displaystyle v}$ ${\displaystyle )}$ ${\displaystyle x=f(v)}$ 및$$ $y{\displaystyle }$= ${\displaystyle f}$(${\displaystyle u}$ ${\displaystyle )}$. ${\displaystyle y=f(u$)를 두십시오$.$$}$ 그런 다음$$ x ${\displaystyle T^{}}$ ${\displaystyle {}^{}}$= ${\displaystyle 0,}$ ${\displaystyle$ x$^{\text{$${\displaystyle T}$$}}y=0,}$ x ${\displaystyle x}$ $및$ y${\displaystyle }$. ${\displaystyle y$$}$의 (${\displaystyle {}^{}}$${\displaystyle }$-$1 ){\displaystyle$ y$}$$$-ball에$$놓여 있는 꼭지점이 없기 때문이기도$$ 하다$$$.$$T}}$ ${\displaystyle x}$의${\displaystyle }$(${\displaystyle r}$${\displaystyle }$- 1${\displaystyle }$) ${\displaystyle$($r-1)}$ -ball에$$ 정점이 없으므로 Aay$$=$0$${\displaystyle ,\}}$ ${\displaystyle \mathrm{-ball}}$은 y$$ .${\displaystyle }$${\displaystyle$$$y$.}$의 정점에 인접할 수$$ 없다.

$현재{\displaystyle }$ z${\displaystyle }$= ${\displaystyle x}$- ${\displaystyle c}$ ${\displaystyle y}$ ${\displaystyle z=x-cy}$이(가) $z{\displaystyle {}^{}}$ ${\displaystyle T^{}}$ ${\displaystyle {}^{}\mathbf{}}$= ${\displaystyle 0}$을 만족하는$$ $상수{\displaystyle }$ c ${\$$displaystyle z^{\text}$이$($가) 존재한다$.$$T}}\mathbf{1} =0.}$ 그러면$$ x ${\displaystyle {}^{}}$ y${\displaystyle }$= ${\displaystyle \mathrm{x}}$ T ${\displaystyle {}^{}}$ ${\displaystyle y}$= 0${\displaystyle ,}$ ${\displaystyle$ x$^{\text{$$T}}y=x^{\text{$$T}}에이=0,}$

${\displaystyle z^{\text}T}}Az=x^{\text{T}}Ax+c^{2}y^{\text{T}}Ay\geq 2{\sqrt{d-1}\왼쪽(1-{\frac {1}{2r}\오른쪽)(x^{\text{T}}x+c^{2}y^{\text{T}}Y)=2{\sqrt{d-1}\왼쪽(1-{\frac {1}{2r}\오른쪽)z^{\text{T}z.}$

Finally, letting ${\displaystyle r}$ grow without bound while ensuring that ${\displaystyle n\geq d^{2r-1}+2}$ (this can be done by letting ${\displaystyle r}$ grow sublogarithmically as a function of ${\displaystyle n}$) makes the error term ${\displaystyle o(1)}$ in ${\dis$$플레이 스타일 n.}$

두 번째 증거(약간 수정된 진술)

This proof will demonstrate a slightly modified result, but it provides better intuition for the source of the number ${\displaystyle 2{\sqrt {d-1}}.}$ Rather than showing that ${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1),}$ we will show that ${\displaystyle \lambda =max({\lambda }_2,{\lambda }_{}}$${\displaystyle \lambda =\max(\da _{2}, \$$d-1-o(1).$$}$

먼저 일부 값 $k{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle N\mathbb{}}$. ${\displaystyle k\in \mathb {N}을($를) 선택하십시오. $길이$가 ${\displaystyle \mathrm{2k}}${\$displaystyle 2k}$인 닫힌 보행 수는

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

그러나 $d{\displaystyle }$ ${\displaystyle d}$ -정규$$ 그래프의 고정$$ 꼭지점 $v{\displaystyle }$ ${\displaystyle v}$에서 시작하는$$ 길이 ${\displaystyle \mathrm{2k}}$ ${\displaystyle 2k}$의 폐쇄된 보행 수는 무한 $d{\displaystyle }$ ${\displaystyle d}$ -정규수에서$$$$ 최소한 그러한 보행의 $수인{\displaystyle }$ 것도 사실이다.나무는 그래프를 덮는 데 사용될 수 있다.By the definition of the Catalan numbers, this number is at least ${\displaystyle C_{k}d(d-1)^{k},}$ where ${\displaystyle C_{k}={\frac {1}{k+1}}{\binom {2k}{k}}}$ is the ${\displaystyle k^{\text{th}}}$ Catalan number.

그 뒤를 잇는다.

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

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

$n{\displaystyle }$ ${\$$displaystyle n}$을(를) 경계 없이 성장하게$$ 하고 $k{\displaystyle }$ ${\displaystyle k}$을(를$)$ n {\$displaystyle n}$에서 제한 없이 하위 로거로 성장시키면$$ ${\displaystyle \mathrm{yields<img\; alt="n"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b"\; style="vertical-align:\; -0.338ex;\; width:1.395ex;\; height:1.676ex;"\; papago-attr-id="320">}}2{\displaystyle }$ d -${\displaystyle \sqrt{}1\sqrt{}}$ -${\displaystyle \mathrm{o}}$ (${\displaystyle }$1 )${\displaystyle }$.${\displaysty \lambda \geq$ 2${\sqrt{d-1-o$(1)-$o.$$}$

참조