Grafo de Ramanujan

En la teoría de grafos espectrales, un grafo de Ramanujan, es un grafo regular cuya brecha espectral es casi tan grande como sea posible (véase la teoría de grafos extremos). Tales grafos son excelentes expansores espectrales. Como señala el estudio de Murty, los grafos de Ramanujan "fusionan diversas ramas de las matemáticas puras, a saber, la teoría de números, la teoría de la representación y la geometría algebraica". Estos grafos llevan el nombre en referencia a Srinivasa Ramanujan; el nombre proviene de la conjetura de Ramanujan-Petersson, que se utilizó en la construcción de algunos de estos gráficos.

Definición

Sea $G$ un grafo conectado $d$-regular con $n$ vértices, y sean $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ los valores propios de la matriz de adyacencia de $G$ (o el espectro de $G$). Dado que $G$ está conectado y es $d$-regular, sus valores propios satisfacen que $d=\lambda _{1}>\lambda _{2}$$\geq \cdots \geq \lambda _{n}\geq -d$ .

Ahora se define $\lambda (G)=\max _{i\neq 1}|\lambda _{i}|=\max(|\lambda _{2}|,|\lambda _{n}|)$. Un grafo conectado $d$-regular $G$ es un grafo de Ramanujan si $\lambda (G)\leq 2{\sqrt {d-1}}$ .

Muchas fuentes usan una definición alternativa para definir los grafos de Ramanujan, mediante la expresión $\lambda '(G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|$ (siempre que exista $\lambda _{i}$ con $|\lambda _{i}|<d$).​ En otras palabras, se permite $-d$ además de los valores propios "pequeños". Ya que $\lambda _{n}=-d$ si y solo si el grafo es bipartito, el artículo se refiere a los grafos que satisfacen esta definición alternativa, pero no a los grafos bipartitos de Ramanujan según la primera definición.

Como observó Toshikazu Sunada, un grafo regular es de Ramanujan si y solo si su función zeta de Ihara satisface un análogo de la hipótesis de Riemann.​

Ejemplos y construcciones

El grafo completo $K_{d+1}$ tiene espectro $d,-1,-1,\dots ,-1$, y por lo tanto $\lambda (K_{d+1})=1$, y entonces el grafo es un grafo de Ramanujan para cada $d>1$. El grafo bipartito completo $K_{d,d}$ tiene espectro $d,0,0,\dots ,0,-d$ y por lo tanto, es un grafo bipartito de Ramanujan para cada $d$.

El gráfico de Petersen tiene espectro $3,1,1,1,1,1,-2,-2,-2,-2$, por lo que es un grafo de Ramanujan 3-regular. El grafo icosaédrico es un grafo de Ramanujan 5-regular.​

Un grafo de Paley de orden $q$ es ${\frac {q-1}{2}}$-regular con todos los demás valores propios, con ${\frac {-1\pm {\sqrt {q}}}{2}}$ haciendo que los grafos de Paley sean una familia infinita de grafos de Ramanujan.

Los matemáticos a menudo están interesados en construir grafos de Ramanujan $d$-regulares para cada $d$ fijo. Las construcciones actuales de familias infinitas de tales grafos de Ramanujan son a menudo algebraicas.

• Lubotzky, Phillips y Sarnak​ demostraron cómo construir una familia infinita de grafos de Ramanujan $(p+1)$-regulares, siempre que $p$ sea un número primo y $p\equiv 1{\pmod {4}}$. Su prueba utiliza la conjetura de Ramanujan, circunstancia que llevó a adoptar el nombre de grafos de Ramanujan. Además de ser grafos de Ramanujan, su construcción satisface algunas otras propiedades, por ejemplo, su circunferencia es $\Omega (\log _{p}(n))$ dónde $n$ es el número de nodos
• Morgenstern​ extendió la construcción de Lubotzky, Phillips y Sarnak. Su construcción extendida se mantiene siempre que $p$ sea una potencia prima.
• Arnold Pizer demostró que los grafos de isogenia supersingular son de Ramanujan, aunque tienden a tener una circunferencia menor que los grafos de Lubotzky, Phillips y Sarnak.​ Al igual que los grafos de Lubotzky, Phillips y Sarnak, los grados de estos grafos son siempre un número primo más uno. Estos gráficos se han propuesto como base para la criptografía de curva elíptica post-cuántica.​
• Adam Marcus, Daniel Spielman y Nikhil Srivastava​ demostraron la existencia de infinitos grafos bipartitos de Ramanujan $d$-regulares para cualquier $d\geq 3$. Más tarde ​ demostraron que existen grafos bipartitos de Ramanujan de cada grado y cada número de vértices. Michael B. Cohen​ demostró cómo construir estos grafos en tiempo polinómico.

Sigue siendo un problema abierto si hay infinitos grafos de Ramanujan $d$-regulares (no bipartitos) para cualquier $d\geq 3$. En particular, el problema está abierto para $d=7$, el caso más pequeño para el cual $d-1$ no es una potencia prima y, por lo tanto, no está cubierto por la construcción de Morgenstern.

Grafos de Ramanujan como grafos expansores

La constante $2{\sqrt {d-1}}$ en la definición de los grafos de Ramanujan es la mejor constante posible para cada $d$ y para grafos grandes. En otras palabras, para cada $d$ y $\epsilon >0$, existe un $n$ tal que todos grafos $d$-regulares $G$ con al menos $n$ vértices satisfacen que $\lambda (G)>2{\sqrt {d-1}}-\epsilon$ (véanse más abajo declaraciones más precisas y esbozos de demostración). Por otro lado, Friedman​ demostró que por cada $d$ y $\epsilon >0$ y para un $n$ suficientemente grande, cualquier grafo $G$ $d$-regular de $n$ vértices satisface que$\lambda (G)<2{\sqrt {d-1}}+\epsilon$ con alta probabilidad. Esto significa que los grafos de Ramanujan son esencialmente los mejores grafos expansores posibles.

Cuando se necesita obtener un límite ajustado en $\lambda (G)$, el lema de mezcla del expansor proporciona límites excelentes en la uniformidad de la distribución de los contornos en los grafos de Ramanujan, y cualquier recorrido aleatorio en estos grafos posee un tiempo de mezcla logarítmico (en términos del número de vértices): en otras palabras, el recorrido aleatorio converge a la distribución estacionaria (uniforme) muy rápidamente. Por lo tanto, el diámetro de los gráficos de Ramanujan también está limitado logarítmicamente en términos del número de vértices.

Extremalidad de los gráficos de Ramanujan

Si $G$ es un grafo $d$-regular con diámetro $m$, un teorema debido a Noga Alon establece que​

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

Cuando $G$ es $d$ -regular y está conectado en al menos tres vértices, $|\lambda _{2}|<d$, y por lo tanto $\lambda (G)\geq \lambda _{2}$. Sea ${\mathcal {G}}_{n}^{d}$ el conjunto de todos los grafos conectados $d$-regulares $G$ con al menos $n$ vértices. Dado que el diámetro mínimo de los grafos en ${\mathcal {G}}_{n}^{d}$ se acerca al infinito para $d$ fijo, y aumentando $n$, este teorema implica un teorema anterior de Alon y Boppana ​ que establece que

$\lim _{n\to \infty }\inf _{G\in {\mathcal {G}}_{n}^{d}}\lambda (G)\geq 2{\sqrt {d-1}}.$

Un límite ligeramente más fuerte es

$\lambda _{2}(G)\geq 2{\sqrt {d-1}}\cdot \left(1-{\frac {c}{m^{2}}}\right),$

donde $c\approx 2\pi ^{2}$ . El bosquejo de la prueba es el siguiente. Tómese $k=\left\lfloor {\frac {m}{2}}\right\rfloor -1$. Sea $T_{d,k}$ el árbol completo $(d-1)$-ario de altura $k$ (cada vértice interno tiene $d-1$ hijos), y sea $A_{d,k}$ su matriz de adyacencia. Se quiere demostrar que $\lambda _{2}(G)\geq \lambda _{1}(T_{d,k})=2{\sqrt {d-1}}\cos \theta$, donde $\theta ={\frac {\pi }{k+2}}$. Ahora, se define una función $g:V(T_{d,k})\rightarrow \mathbb {R}$ por $g(x)=(d-1)^{-\delta /2}\cdot \sin((k+1-\delta )\theta )$, donde $\delta$ es la distancia desde $x$ a la raíz de $T_{d,k}$. Se puede verificar que $A_{t,k}g=\lambda _{1}(T_{d,k})g$ y que $\lambda _{1}(T_{d,k})$ es de hecho el mayor valor propio de $A_{d,k}$. Ahora, sean $s$ y $t$ un par de vértices a distancia $m$ en $G$, y se define

$f(v)={\begin{cases}c_{1}g(v_{s})&{\text{for }}v{\text{ at distance }}\leq k{\text{ from }}s,\\-c_{2}g(v_{t})&{\text{for }}v{\text{ at distance }}\leq k{\text{ from }}t,\\0&{\text{otherwise,}}\end{cases}}$

donde $v_{s}$ es un vértice en $T_{d,k}$ cuya distancia a la raíz es igual a la distancia desde $v$ a $s$ y la simétrica para $v_{t}$. Se puede pensar en esto como "incrustar" dos copias disjuntas de $T_{d,k}$, con algunos vértices colapsados en uno. Al elegir el valor de los reales positivos $c_{1},c_{2}$ adecuadamente se obtiene $f\perp 1$, $(Af)_{v}\geq \lambda _{1}(T_{d,k})f_{v}$ para $v$ cerca de $s$ y $(Af)_{v}\leq \lambda _{1}(T_{d,k})f_{v}$ para $v$ cerca de $t$. Entonces por el teorema mini-máx se obtiene

$$\lambda _{2}(G)\geq fAf^{T}/\|f\|^{2}\geq \lambda _{1}(T_{d,k})\approx 2{\sqrt {d-1}}\left(1-{\frac {1}{2}}\left({\frac {2\pi }{m}}\right)^{2}\right),$$

tal como se pretendía

Véase también

• Gráfico expansor
• Lema del mezclador expansor
• Teoría del grafo espectral

Lecturas relacionadas

• Guiliana Davidoff; Peter Sarnak; Alain Valette (2003). Elementary number theory, group theory and Ramanjuan graphs. LMS student texts 55. Cambridge University Press. ISBN 0-521-53143-8. OCLC 50253269. 
• T. Sunada (1985). «L-functions in geometry and some applications». Lecture Notes in Math. Lecture Notes in Mathematics 1201: 266-284. ISBN 978-3-540-16770-9. doi:10.1007/BFb0075662. 

Enlaces externos

• Documento de encuesta de M. Ram Murty