Grafo de Ramanujan

Ir a la navegaciónIr a la búsqueda

Grafo de Pappus: un grafo regular, formado por 18 vértices, todos ellos enlazados
con otros tres vértices
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.

Índice
1 Definición
2 Ejemplos y construcciones
3 Grafos de Ramanujan como grafos expansores
3.1 Extremalidad de los grafos de Ramanujan
4 Ejemplo numérico
5 Véase también
6 Referencias
7 Lecturas relacionadas
8 Enlaces externos
Definición
Sea {\displaystyle G}G un grafo conectado {\displaystyle d}d-regular con
{\displaystyle n}n vértices, y sean {\displaystyle \lambda _{1}\geq \lambda
_{2}\geq \cdots \geq \lambda _{n}}{\displaystyle \lambda _{1}\geq \lambda
_{2}\geq \cdots \geq \lambda _{n}} los valores propios de la matriz de adyacencia
de {\displaystyle G}G (o el espectro de {\displaystyle G}G). Dado que
{\displaystyle G}G está conectado y es {\displaystyle d}d-regular, sus valores
propios satisfacen que {\displaystyle d=\lambda _{1}>\lambda _{2}}{\displaystyle
d=\lambda _{1}>\lambda _{2}}{\displaystyle \geq \cdots \geq \lambda _{n}\geq -d}
{\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}|)}{\displaystyle \lambda (G)=\max _{i\neq
1}|\lambda _{i}|=\max(|\lambda _{2}|,|\lambda _{n}|)}. Un grafo conectado
{\displaystyle d}d-regular {\displaystyle G}G es un grafo de Ramanujan si
{\displaystyle \lambda (G)\leq 2{\sqrt {d-1}}}{\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}|}
{\displaystyle \lambda '(G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|} (siempre que
exista {\displaystyle \lambda _{i}}{\displaystyle \lambda _{i}} con {\displaystyle
|\lambda _{i}|<d}{\displaystyle |\lambda _{i}|<d}).1 En otras palabras, se permite
{\displaystyle -d}{\displaystyle -d} además de los valores propios "pequeños". Ya
que {\displaystyle \lambda _{n}=-d}{\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}}{\displaystyle K_{d+1}} tiene espectro
{\displaystyle d,-1,-1,\dots ,-1}{\displaystyle d,-1,-1,\dots ,-1}, y por lo tanto
{\displaystyle \lambda (K_{d+1})=1}{\displaystyle \lambda (K_{d+1})=1}, y entonces
el grafo es un grafo de Ramanujan para cada {\displaystyle d>1}{\displaystyle d>1}.
El grafo bipartito completo {\displaystyle K_{d,d}}{\displaystyle K_{d,d}} tiene
espectro {\displaystyle d,0,0,\dots ,0,-d}{\displaystyle d,0,0,\dots ,0,-d} y por
lo tanto, es un grafo bipartito de Ramanujan para cada {\displaystyle d}d.

El gráfico de Petersen tiene espectro {\displaystyle 3,1,1,1,1,1,-2,-2,-2,-2}

{\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}q es {\displaystyle {\frac {q-1}{2}}}

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

Lubotzky, Phillips y Sarnak1 demostraron cómo construir una familia infinita de

grafos de Ramanujan {\displaystyle (p+1)}{\displaystyle (p+1)}-regulares, siempre
que {\displaystyle p}p sea un número primo y {\displaystyle p\equiv 1{\pmod {4}}}
{\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))}
{\displaystyle \Omega (\log _{p}(n))} dónde {\displaystyle n}n es el número de
nodos
Morgenstern4 extendió la construcción de Lubotzky, Phillips y Sarnak. Su
construcción extendida se mantiene siempre que {\displaystyle p}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 Srivastava7 demostraron la existencia de
infinitos grafos bipartitos de Ramanujan {\displaystyle d}d-regulares para
cualquier {\displaystyle d\geq 3}{\displaystyle d\geq 3}. Más tarde8 demostraron
que existen grafos bipartitos de Ramanujan de cada grado y cada número de vértices.
Michael B. Cohen9 demostró cómo construir estos grafos en tiempo polinómico.
Sigue siendo un problema abierto si hay infinitos grafos de Ramanujan
{\displaystyle d}d-regulares (no bipartitos) para cualquier {\displaystyle d\geq 3}
{\displaystyle d\geq 3}. En particular, el problema está abierto para
{\displaystyle d=7}{\displaystyle d=7}, el caso más pequeño para el cual
{\displaystyle d-1}{\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}}}{\displaystyle 2{\sqrt {d-1}}} en la
definición de los grafos de Ramanujan es la mejor constante posible para cada
{\displaystyle d}d y para grafos grandes. En otras palabras, para cada
{\displaystyle d}d y {\displaystyle \epsilon >0}\epsilon > 0, existe un
{\displaystyle n}n tal que todos grafos {\displaystyle d}d-regulares {\displaystyle
G}G con al menos {\displaystyle n}n vértices satisfacen que {\displaystyle \lambda
(G)>2{\sqrt {d-1}}-\epsilon }{\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, Friedman10 demostró que por cada {\displaystyle d}d y {\displaystyle \epsilon
>0}\epsilon > 0 y para un {\displaystyle n}n suficientemente grande, cualquier
grafo {\displaystyle G}G {\displaystyle d}d-regular de {\displaystyle n}n vértices
satisface que{\displaystyle \lambda (G)<2{\sqrt {d-1}}+\epsilon }{\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)}

{\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}G es un grafo {\displaystyle d}d-regular con diámetro
{\displaystyle m}m, un teorema debido a Noga Alon establece que11

{\displaystyle \lambda _{2}(G)\geq 2{\sqrt {d-1}}-{\frac {2{\sqrt {d-1}}-1}{\lfloor

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

{\displaystyle \lim _{n\to \infty }\inf _{G\in {\mathcal {G}}_{n}^{d}}\lambda

(G)\geq 2{\sqrt {d-1}}.}{\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),}{\displaystyle \lambda _{2}(G)\geq 2{\sqrt {d-1}}\cdot \left(1-
{\frac {c}{m^{2}}}\right),}
donde {\displaystyle c\approx 2\pi ^{2}}{\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}{\displaystyle k=\left\lfloor {\frac {m}{2}}\right\rfloor
-1}. Sea {\displaystyle T_{d,k}}{\displaystyle T_{d,k}} el árbol completo
{\displaystyle (d-1)}{\displaystyle (d-1)}-ario de altura {\displaystyle k}k (cada
vértice interno tiene {\displaystyle d-1}{\displaystyle d-1} hijos), y sea
{\displaystyle A_{d,k}}{\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 }{\displaystyle \lambda _{2}(G)\geq \lambda _{1}(T_{d,k})=2{\sqrt
{d-1}}\cos \theta }, donde {\displaystyle \theta ={\frac {\pi }{k+2}}}
{\displaystyle \theta ={\frac {\pi }{k+2}}}. Ahora, se define una función
{\displaystyle g:V(T_{d,k})\rightarrow \mathbb {R} }{\displaystyle
g:V(T_{d,k})\rightarrow \mathbb {R} } por {\displaystyle g(x)=(d-1)^{-\delta
/2}\cdot \sin((k+1-\delta )\theta )}{\displaystyle g(x)=(d-1)^{-\delta /2}\cdot
\sin((k+1-\delta )\theta )}, donde {\displaystyle \delta }\delta es la distancia
desde {\displaystyle x}x a la raíz de {\displaystyle T_{d,k}}{\displaystyle
T_{d,k}}. Se puede verificar que {\displaystyle A_{t,k}g=\lambda _{1}(T_{d,k})g}
{\displaystyle A_{t,k}g=\lambda _{1}(T_{d,k})g} y que {\displaystyle \lambda _{1}
(T_{d,k})}{\displaystyle \lambda _{1}(T_{d,k})} es de hecho el mayor valor propio
de {\displaystyle A_{d,k}}{\displaystyle A_{d,k}}. Ahora, sean {\displaystyle s}s y
{\displaystyle t}t un par de vértices a distancia {\displaystyle m}m en
{\displaystyle G}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}}}
{\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}}{\displaystyle v_{s}} es un vértice en {\displaystyle
T_{d,k}}{\displaystyle T_{d,k}} cuya distancia a la raíz es igual a la distancia
desde {\displaystyle v}v a {\displaystyle s}s y la simétrica para {\displaystyle
v_{t}}{\displaystyle v_{t}}. Se puede pensar en esto como "incrustar" dos copias
disjuntas de {\displaystyle T_{d,k}}{\displaystyle T_{d,k}}, con algunos vértices
colapsados en uno. Al elegir el valor de los reales positivos {\displaystyle
c_{1},c_{2}}{\displaystyle c_{1},c_{2}} adecuadamente se obtiene {\displaystyle
f\perp 1}{\displaystyle f\perp 1}, {\displaystyle (Af)_{v}\geq \lambda _{1}
(T_{d,k})f_{v}}{\displaystyle (Af)_{v}\geq \lambda _{1}(T_{d,k})f_{v}} para
{\displaystyle v}v cerca de {\displaystyle s}s y {\displaystyle (Af)_{v}\leq
\lambda _{1}(T_{d,k})f_{v}}{\displaystyle (Af)_{v}\leq \lambda _{1}(T_{d,k})f_{v}}
para {\displaystyle v}v cerca de {\displaystyle t}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),}
{\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}}{\displaystyle \lambda _{i}} de la matriz
de adyacencia {\displaystyle A}A, que cumplen con la propiedad de que:

{\displaystyle \det(A-\lambda I)=0\!\ }\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}}{\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}}}{\displaystyle -{\sqrt {3}}};
cuatro veces 0; seis veces {\displaystyle {\sqrt {3}}}{\displaystyle {\sqrt {3}}};
y por último, una vez 3
De acuerdo con la definición de partida, todos los {\displaystyle \lambda _{i}}
{\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
Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). «Ramanujan graphs».
Combinatorica 8 (3): 261-277. doi:10.1007/BF02126799.
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.
Weisstein, Eric W. «Icosahedral Graph». [Link] (en inglés).
Consultado el 29 de noviembre de 2019.
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.
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.
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.
Adam Marcus (2013). Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual
Symposium.
Adam Marcus (2015). Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual
Symposium.
Michael B. Cohen (2016). Foundations of Computer Science (FOCS), 2016 IEEE 57th
Annual Symposium. doi:10.1109/FOCS.2016.37.
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.
Nilli, A. (1991), «On the second eigenvalue of a graph», Discrete Mathematics 91
(2): 207-210, doi:10.1016/0012-365X(91)90112-F..
Alon, N. (1986). «Eigenvalues and expanders». Combinatorica 6 (2): 83-96.
doi:10.1007/BF02579166.