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 extremales). 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". Llevan este nombre en referencia a Srinivasa Ramanujan; y proviene de la conjetura de Ramanujan–Petersson, que se utilizó en la construcción de algunos de estos gráficos.

Grafo de Pappus: un grafo regular, formado por 18 vértices, todos ellos enlazados con otros tres vértices

Definición

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

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

Muchas fuentes usan una definición alternativa de los grafos de Ramanujan, mediante la expresión ${\displaystyle \lambda '(G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|}$  (siempre que exista ${\displaystyle \lambda _{i}}$  con ${\displaystyle |\lambda _{i}|<d}$ ).^[1]​ En otras palabras, se permite ${\displaystyle -d}$  además de los valores propios "pequeños". Ya que ${\displaystyle \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.^[2]​

Ejemplos y construcciones

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

El gráfico de Petersen tiene espectro ${\displaystyle 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.^[3]​

Un grafo de Paley de orden ${\displaystyle q}$  es ${\displaystyle {\frac {q-1}{2}}}$ -regular con todos los demás valores propios, con ${\displaystyle {\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 ${\displaystyle d}$ -regulares para cada ${\displaystyle d}$  fijo. Las construcciones actuales de familias infinitas de tales grafos de Ramanujan son a menudo algebraicas.

• Lubotzky, Phillips y Sarnak^[1]​ demostraron cómo construir una familia infinita de grafos de Ramanujan ${\displaystyle (p+1)}$ -regulares, siempre que ${\displaystyle p}$  sea un número primo y ${\displaystyle 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 ${\displaystyle \Omega (\log _{p}(n))}$  dónde ${\displaystyle n}$  es el número de nodos
• Morgenstern^[4]​ extendió la construcción de Lubotzky, Phillips y Sarnak. Su construcción extendida se mantiene siempre que ${\displaystyle 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.^[5]​ 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.^[6]​
• Adam Marcus, Daniel Spielman y Nikhil Srivastava^[7]​ demostraron la existencia de infinitos grafos bipartitos de Ramanujan ${\displaystyle d}$ -regulares para cualquier ${\displaystyle d\geq 3}$ . Más tarde^[8]​ demostraron que existen grafos bipartitos de Ramanujan de cada grado y cada número de vértices. Michael B. Cohen^[9]​ demostró cómo construir estos grafos en tiempo polinómico.

Sigue siendo un problema abierto si hay infinitos grafos de Ramanujan ${\displaystyle d}$ -regulares (no bipartitos) para cualquier ${\displaystyle d\geq 3}$ . En particular, el problema está abierto para ${\displaystyle d=7}$ , el caso más pequeño para el cual ${\displaystyle 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 ${\displaystyle 2{\sqrt {d-1}}}$  en la definición de los grafos de Ramanujan es la mejor constante posible para cada ${\displaystyle d}$  y para grafos grandes. En otras palabras, para cada ${\displaystyle d}$  y ${\displaystyle \epsilon >0}$ , existe un ${\displaystyle n}$  tal que todos grafos ${\displaystyle d}$ -regulares ${\displaystyle G}$  con al menos ${\displaystyle n}$  vértices satisfacen que ${\displaystyle \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^[10]​ demostró que por cada ${\displaystyle d}$  y ${\displaystyle \epsilon >0}$  y para un ${\displaystyle n}$  suficientemente grande, cualquier grafo ${\displaystyle G}$  ${\displaystyle d}$ -regular de ${\displaystyle n}$  vértices satisface que${\displaystyle \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 ${\displaystyle \lambda (G)}$ , el lema del 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 grafos de Ramanujan

Si ${\displaystyle G}$  es un grafo ${\displaystyle d}$ -regular con diámetro ${\displaystyle m}$ , un teorema debido a Noga Alon establece que^[11]​

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

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

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

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

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

${\displaystyle f(v)={\begin{cases}c_{1}g(v_{s})&{\text{para }}v{\text{ a la distancia }}\leq k{\text{ desde }}s,\\-c_{2}g(v_{t})&{\text{para }}v{\text{ a la distancia }}\leq k{\text{ desde }}t,\\0&{\text{en otro caso,}}\end{cases}}}$ 

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

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

Ejemplo numérico

 

Grafo de Pappus (3-regular con 18 vértices). Se comprueba que es un grafo de Ramanujan mediante el análisis de los autovalores de su matriz de adyacencia

El gráfico de Pappus es un polígono regular de 18 vértices, en el que cada vértice, además de con sus dos vértices adyacentes, está conectado con un tercer vértice guardando una determinada configuración.

Esto implica que se trata de un grafo 3-regular, formado por 18 vértices. Para comprobar que se trata de un grafo de Ramanujan, es necesario construir su matriz de adyacencia, y analizar sus autovalores. Para ello, se parte de una matriz de 18x18 (inicialmente con todas sus celdas con valor 0), y se van situando valores 1 en las celdas que se correspondan con alguna conexión en el gráfico. Por ejemplo, la fila 4 tiene rellenadas con 1 las columnas 3 y 5 (los dos vértices adyacentes al vértice 4 en el perímetro del polígono) y la columna 15 (correspondiente a la conexión entre los vértices 4 y 15). Una vez completado este proceso de rellenado de filas para los 18 vértices, se obtiene una matriz que dadas las condiciones del polígono, es simétrica, y posee tres celdillas con el número 1 en cada fila y en cada columna.

Para confirmar si se trata de un grafo de Ramanujan, es necesario determinar los autovalores ${\displaystyle \lambda _{i}}$  de la matriz de adyacencia ${\displaystyle A}$ , que cumplen con la propiedad de que:

${\displaystyle \det(A-\lambda I)=0\!\ }$ 

Para ello, se ha utilizado el programa "MATLAB", diseñado para trabajar con matrices. Determinar estos 18 ${\displaystyle \lambda _{i}}$  equivale a resolver un polinomio de grado 18, calculando sus 18 raíces. Dada la gran simetría de la matriz, el cálculo de los autovalores arroja el resultado siguiente:

• Una vez -3; seis veces ${\displaystyle -{\sqrt {3}}}$ ; cuatro veces 0; seis veces ${\displaystyle {\sqrt {3}}}$ ; y por último, una vez 3

De acuerdo con la definición de partida, todos los ${\displaystyle \lambda _{i}}$  están comprendidos entre +d y -d, y dado que d vale 3, queda demostrado que el polígono de Pappus es un grafo de Ramanujan.

Véase también

• Grafo expansor
• Lema del mezclador expansor
• Teoría del grafo espectral

Referencias

1. Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). «Ramanujan graphs». Combinatorica 8 (3): 261-277. doi:10.1007/BF02126799. 
2. Terras, Audrey (2011), Zeta functions of graphs: A stroll through the garden, Cambridge Studies in Advanced Mathematics 128, Cambridge University Press, ISBN 978-0-521-11367-0 .
3. Weisstein, Eric W. «Icosahedral Graph». mathworld.wolfram.com (en inglés). Consultado el 29 de noviembre de 2019. 
4. Moshe Morgenstern (1994). «Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q». Journal of Combinatorial Theory, Series B 62: 44-62. doi:10.1006/jctb.1994.1054. 
5. Pizer, Arnold K. (1990), «Ramanujan graphs and Hecke operators», Bulletin of the American Mathematical Society, New Series 23 (1): 127-137, doi:10.1090/S0273-0979-1990-15918-X .
6. Eisenträger, Kirsten; Hallgren, Sean; Lauter, Kristin; Morrison, Travis; Petit, Christophe (2018), «Supersingular isogeny graphs and endomorphism rings: Reductions and solutions», en Nielsen, Jesper Buus; Rijmen, Vincent, eds., Advances in Cryptology – EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018, Proceedings, Part III, Lecture Notes in Computer Science 10822, Cham: Springer, pp. 329-368, doi:10.1007/978-3-319-78372-7_11 .
7. Adam Marcus (2013). Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium. 
8. Adam Marcus (2015). Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium. 
9. Michael B. Cohen (2016). Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium. doi:10.1109/FOCS.2016.37. 
10. Friedman, Joel (2003). «Relative expanders or weakly relatively Ramanujan graphs». Duke Math. J. 118 (1): 19-35. doi:10.1215/S0012-7094-03-11812-8. 
11. Nilli, A. (1991), «On the second eigenvalue of a graph», Discrete Mathematics 91 (2): 207-210, doi:10.1016/0012-365X(91)90112-F ..
12. Alon, N. (1986). «Eigenvalues and expanders». Combinatorica 6 (2): 83-96. doi:10.1007/BF02579166. 

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

•   Datos: Q3115527