Con destino a Alon y Boppana

En la teoría de grafos espectrales , el límite de Alon-Boppana proporciona un límite inferior para el segundo valor propio más grande de la matriz de adyacencia de un grafo -regular, ^[1] es decir, un grafo en el que cada vértice tiene grado . La razón del interés en el segundo valor propio más grande es que se garantiza que el valor propio más grande se debe a la -regularidad, siendo el vector de todos unos el vector propio asociado. Los grafos que se acercan a cumplir con este límite son los grafos de Ramanujan , que son ejemplos de los mejores grafos expansores posibles . ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$

Sus descubridores son Noga Alon y Ravi Boppana.

Enunciado del teorema

Sea un grafo regular sobre vértices con diámetro , y sea su matriz de adyacencia. Sean sus valores propios. Entonces ${\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 }}.}$

La afirmación anterior es la original que demostró Noga Alon . Existen algunas variantes ligeramente más débiles para mejorar la facilidad de la demostración o la intuición. Dos de ellas se muestran en las pruebas que aparecen a continuación.

Intuición

El gráfico de Cayley del grupo libre en dos generadores es un ejemplo de un árbol infinito -regular para ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle d}$ ${\displaystyle d=4.}$

La intuición del número proviene de considerar el árbol infinito -regular. ^[2] Este gráfico es una cubierta universal de gráficos -regulares y tiene un radio espectral ${\displaystyle 2{\sqrt {d-1}}}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle 2{\sqrt {d-1}}.}$

Saturación

Un gráfico que esencialmente satura el límite de Alon-Boppana se denomina gráfico de Ramanujan . Más precisamente, un gráfico de Ramanujan es un gráfico -regular tal que ${\displaystyle d}$ ${\displaystyle |\lambda _{2}|,|\lambda _{n}|\leq 2{\sqrt {d-1}}.}$

Un teorema de Friedman ^[3] muestra que, para cada y y para , un grafo aleatorio -regular sobre vértices satisface con alta probabilidad . Esto significa que un grafo aleatorio -vértice -regular es típicamente "casi Ramanujan". ${\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}$

Primera prueba (afirmación ligeramente más débil)

Probaremos una afirmación ligeramente más débil, es decir, eliminando la especificidad en el segundo término y simplemente afirmando: Aquí, el término se refiere al comportamiento asintótico que crece sin límite mientras permanece fijo. ${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1).}$ ${\displaystyle o(1)}$ ${\displaystyle n}$ ${\displaystyle d}$

Sea el conjunto de vértices Por el teorema mínimo-máximo , basta con construir un vector distinto de cero tal que y ${\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).}$

Elija un valor Para cada vértice en defina un vector de la siguiente manera. Cada componente será indexado por un vértice en el gráfico. Para cada si la distancia entre y es entonces el componente de es si y si Afirmamos que cualquier vector de este tipo satisface ${\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).}$

Para demostrar esto, denotemos el conjunto de todos los vértices que tienen una distancia de exactamente desde Primero, note que ${\displaystyle V_{k}}$ ${\displaystyle k}$ ${\displaystyle v.}$

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

En segundo lugar, tenga en cuenta que

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

donde el último término de la derecha proviene de un posible recuento excesivo de términos en la expresión inicial. Lo anterior implica entonces

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

lo cual, cuando se combina con el hecho de que para cualquier rendimiento ${\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}.}$

La combinación de los resultados anteriores demuestra la desigualdad deseada.

Para mayor comodidad, defina la -bola de un vértice como el conjunto de vértices con una distancia de como máximo desde Nótese que la entrada de correspondiente a un vértice es distinta de cero si y solo si se encuentra en la -bola de ${\displaystyle (r-1)}$ ${\displaystyle v}$ ${\displaystyle r-1}$ ${\displaystyle v.}$ ${\displaystyle f(v)}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle (r-1)}$ ${\displaystyle x.}$

El número de vértices dentro de la distancia de un vértice dado es como máximo Por lo tanto, si entonces existen vértices con una distancia de al menos ${\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.}$

Sea y Entonces se sigue que debido a que no hay ningún vértice que se encuentre en las bolas de ambos y También es cierto que debido a que ningún vértice en la bola de puede ser adyacente a un vértice en la bola de ${\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.}$

Ahora bien, existe alguna constante tal que satisface Entonces, puesto que ${\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.}$

Finalmente, dejar crecer sin límite mientras se asegura que (esto se puede hacer dejando crecer sublogarítmicamente como una función de ) hace que el término de error en ${\displaystyle r}$ ${\displaystyle n\geq d^{2r-1}+2}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle o(1)}$ ${\displaystyle n.}$

Segunda prueba (afirmación ligeramente modificada)

Esta prueba demostrará un resultado ligeramente modificado, pero proporciona una mejor intuición de la fuente del número. En lugar de mostrar eso, demostraremos que ${\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).}$

Primero, elija un valor. Observe que el número de paseos cerrados de longitud es ${\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}.}$

Sin embargo, también es cierto que el número de recorridos cerrados de longitud que comienzan en un vértice fijo en un grafo -regular es al menos el número de dichos recorridos en un árbol -regular infinito, porque un árbol -regular infinito puede usarse para cubrir el grafo. Por la definición de los números de Catalan , este número es al menos donde es el número de Catalan. ${\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}}}$

Resulta que

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

Dejar crecer sin límite y dejar crecer sin límite pero de forma sublogarítmica en rendimientos ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle \lambda \geq 2{\sqrt {d-1}}-o(1).}$

Referencias

1. Nilli, A. (1991), "Sobre el segundo valor propio de un grafo", Discrete Mathematics , 91 (2): 207–210, doi : 10.1016/0012-365X(91)90112-F , MR  1124768
2. Hoory, S.; Linial, N.; Wigderson, A. (2006), "Gráficos expansores y sus aplicaciones" (PDF) , Bull. Amer. Math. Soc. (NS) , 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8
3. Friedman, Joel (2003). "Expansores relativos o grafos Ramanujan débilmente relativos". Duke Math. J. 118 ( 1): 19–35. doi :10.1215/S0012-7094-03-11812-8. MR  1978881.