Gráfico de Ramanujan

En el campo matemático de la teoría de grafos espectrales , un grafo de Ramanujan es un grafo regular cuyo hueco espectral es casi tan grande como sea posible (ver teoría de grafos extremales ). Tales grafos son excelentes expansores espectrales . Como señala el artículo de investigación de Murty ^[1] , 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 reciben indirectamente su nombre de Srinivasa Ramanujan ; su nombre proviene de la conjetura de Ramanujan-Petersson , que se utilizó en la construcción de algunos de estos grafos.

Definición

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

Definir . Un gráfico regular conexo es un gráfico de Ramanujan si . ${\displaystyle \lambda (G)=\max _{i\neq 1}|\lambda _{i}|=\max(|\lambda _{2}|,\ldots ,|\lambda _{n}|)}$ ${\displaystyle d}$ ${\displaystyle G}$ ${\displaystyle \lambda (G)\leq 2{\sqrt {d-1}}}$

Muchas fuentes utilizan una definición alternativa (siempre que exista con ) para definir los grafos de Ramanujan. ^[2] En otras palabras, permitimos además de los valores propios "pequeños". Dado que si y solo si el grafo es bipartito , nos referiremos a los grafos que satisfacen esta definición alternativa pero no la primera definición grafos de Ramanujan bipartitos . Si es un grafo de Ramanujan, entonces es un grafo de Ramanujan bipartito, por lo que la existencia de grafos de Ramanujan es más fuerte. ${\displaystyle \lambda '(G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|}$ ${\displaystyle \lambda _{i}}$ ${\displaystyle |\lambda _{i}|<d}$ ${\displaystyle -d}$ ${\displaystyle \lambda _{n}=-d}$ ${\displaystyle G}$ ${\displaystyle G\times K_{2}}$

Como observó Toshikazu Sunada , un gráfico regular es Ramanujan si y sólo si su función zeta de Ihara satisface un análogo de la hipótesis de Riemann . ^[3]

Ejemplos y construcciones

Ejemplos explícitos

• El gráfico completo tiene espectro y, por lo tanto , el gráfico es un gráfico de Ramanujan para cada . El gráfico bipartito completo tiene espectro y, por lo tanto, es un gráfico bipartito de Ramanujan para cada . ${\displaystyle K_{d+1}}$ ${\displaystyle d,-1,-1,\dots ,-1}$ ${\displaystyle \lambda (K_{d+1})=1}$ ${\displaystyle d>1}$ ${\displaystyle K_{d,d}}$ ${\displaystyle d,0,0,\dots ,0,-d}$ ${\displaystyle d}$
• El gráfico de Petersen tiene un espectro de , por lo que es un gráfico de Ramanujan de 3 regularidades. El gráfico icosaédrico es un gráfico de Ramanujan de 5 regularidades. ^[4] ${\displaystyle 3,1,1,1,1,1,-2,-2,-2,-2}$
• Un gráfico de Paley de orden es -regular y todos los demás valores propios son , lo que convierte a los gráficos de Paley en una familia infinita de gráficos de Ramanujan. ${\displaystyle q}$ ${\displaystyle {\frac {q-1}{2}}}$ ${\displaystyle {\frac {-1\pm {\sqrt {q}}}{2}}}$
• En términos más generales, sea un polinomio de grado 2 o 3 sobre . Sea la imagen de como un multiconjunto y supongamos que . Entonces, el gráfico de Cayley para con generadores de es un gráfico de Ramanujan. ${\displaystyle f(x)}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle S=\{f(x)\,:\,x\in \mathbb {F} _{q}\}}$ ${\displaystyle f(x)}$ ${\displaystyle S=-S}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle S}$

Los matemáticos suelen estar interesados ​​en construir familias infinitas de grafos Ramanujan regulares para cada . Dichas familias son útiles en aplicaciones. ${\displaystyle d}$ ${\displaystyle d}$

Construcciones algebraicas

Varias construcciones explícitas de grafos de Ramanujan surgen como grafos de Cayley y son de naturaleza algebraica. Véase el estudio de Winnie Li sobre la conjetura de Ramanujan y otros aspectos de la teoría de números relevantes para estos resultados. ^[5]

Lubotzky , Phillips y Sarnak ^[2] e independientemente Margulis ^[6] demostraron cómo construir una familia infinita de grafos de Ramanujan -regulares, siempre que sea un número primo y . Ambas demostraciones utilizan la conjetura de Ramanujan , que dio lugar al nombre de grafos de Ramanujan. Además de ser grafos de Ramanujan, estas construcciones satisfacen algunas otras propiedades, por ejemplo, su circunferencia es donde es el número de nodos. ${\displaystyle (p+1)}$ ${\displaystyle p}$ ${\displaystyle p\equiv 1{\pmod {4}}}$ ${\displaystyle \Omega (\log _{p}(n))}$ ${\displaystyle n}$

Dibujemos la construcción de Lubotzky-Phillips-Sarnak. Sea un primo distinto de . Por el teorema de los cuatro cuadrados de Jacobi , existen soluciones de la ecuación donde es impar y son pares. A cada una de esas soluciones se asocia la matriz Si ​​no es un residuo cuadrático módulo sea el grafo de Cayley de con estos generadores, y en caso contrario, sea el grafo de Cayley de con los mismos generadores. Entonces es un grafo -regular en o vértices dependiendo de si es o no un residuo cuadrático módulo . Se demuestra que es un grafo de Ramanujan. ${\displaystyle q\equiv 1{\bmod {4}}}$ ${\displaystyle p}$ ${\displaystyle p+1}$ ${\displaystyle p=a_{0}^{2}+a_{1}^{2}+a_{2}^{2}+a_{3}^{2}}$ ${\displaystyle a_{0}>0}$ ${\displaystyle a_{1},a_{2},a_{3}}$ ${\displaystyle \operatorname {PGL} (2,\mathbb {Z} /q\mathbb {Z} )}$ $${\displaystyle {\tilde {\alpha }}={\begin{pmatrix}a_{0}+ia_{1}&a_{2}+ia_{3}\\-a_{2}+ia_{3}&a_{0}-ia_{1}\end{pmatrix}},\qquad i{\text{ a fixed solution to }}i^{2}=-1{\bmod {q}}.}$$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle X^{p,q}}$ ${\displaystyle \operatorname {PGL} (2,\mathbb {Z} /q\mathbb {Z} )}$ ${\displaystyle p+1}$ ${\displaystyle X^{p,q}}$ ${\displaystyle \operatorname {PSL} (2,\mathbb {Z} /q\mathbb {Z} )}$ ${\displaystyle X^{p,q}}$ ${\displaystyle (p+1)}$ ${\displaystyle n=q(q^{2}-1)}$ ${\displaystyle q(q^{2}-1)/2}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle X^{p,q}}$

Morgenstern ^[7] luego extendió la construcción de Lubotzky, Phillips y Sarnak. Su construcción extendida es válida siempre que sea una potencia prima . ${\displaystyle p}$

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. ^[8] Al igual que los grafos de Lubotzky, Phillips y Sarnak, los grados de estos grafos son siempre un número primo más uno.

Ejemplos probabilísticos

Adam Marcus , Daniel Spielman y Nikhil Srivastava ^[9] demostraron la existencia de infinitos grafos Ramanujan bipartitos -regulares para cualquier . Más tarde ^[10] demostraron que existen grafos Ramanujan bipartitos de cada grado y cada número de vértices. Michael B. Cohen ^[11] mostró cómo construir estos grafos en tiempo polinomial. ${\displaystyle d}$ ${\displaystyle d\geq 3}$

El trabajo inicial siguió un enfoque de Bilu y Linial . Consideraron una operación llamada 2-lift que toma un grafo -regular con vértices y un signo en cada arista, y produce un nuevo grafo -regular en vértices. Bilu y Linial conjeturaron que siempre existe un signo de modo que cada nuevo valor propio de tiene magnitud como máximo . Esta conjetura garantiza la existencia de grafos de Ramanujan con grado y vértices para cualquier —simplemente comience con el grafo completo y tome iterativamente 2-lifts que conserven la propiedad de Ramanujan. ${\displaystyle d}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle G'}$ ${\displaystyle 2n}$ ${\displaystyle G'}$ ${\displaystyle 2{\sqrt {d-1}}}$ ${\displaystyle d}$ ${\displaystyle 2^{k}(d+1)}$ ${\displaystyle k}$ ${\displaystyle K_{d+1}}$

Utilizando el método de entrelazado de polinomios, Marcus, Spielman y Srivastava ^[9] demostraron que la conjetura de Bilu y Linial es válida cuando ya es un grafo Ramanujan bipartito, lo que es suficiente para concluir el resultado de existencia. La secuela ^[10] demostró la afirmación más sólida de que una suma de emparejamientos bipartitos aleatorios es Ramanujan con probabilidad no nula. Hall, Puder y Sawin ^[12] ampliaron el trabajo original de Marcus, Spielman y Srivastava a los r -lifts. ${\displaystyle G}$ ${\displaystyle d}$

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

Los gráficos de Ramanujan como gráficos expansores

La constante en la definición de los grafos de Ramanujan es asintóticamente aguda. Más precisamente, el límite de Alon-Boppana establece que para cada y , existe tal que todos los grafos -regulares con al menos vértices satisfacen . Esto significa que los grafos de Ramanujan son esencialmente los mejores grafos expansores posibles . ${\displaystyle 2{\sqrt {d-1}}}$ ${\displaystyle d}$ ${\displaystyle \epsilon >0}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \lambda (G)>2{\sqrt {d-1}}-\epsilon }$

Debido a que se logra el límite estricto de , el lema de mezcla del expansor proporciona límites excelentes para la uniformidad de la distribución de las aristas en los grafos de Ramanujan, y cualquier recorrido aleatorio en los grafos tiene 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 grafos de Ramanujan también está acotado logarítmicamente en términos del número de vértices. ${\displaystyle \lambda (G)}$

Gráficos aleatorios

Confirmando una conjetura de Alon , Friedman ^[13] mostró que muchas familias de grafos aleatorios son débilmente Ramanujan . Esto significa que para cada y y para suficientemente grande , un grafo aleatorio -regular -vértice satisface con alta probabilidad. Si bien este resultado muestra que los grafos aleatorios están cerca de ser Ramanujan, no se puede utilizar para probar la existencia de grafos Ramanujan. Sin embargo, se conjetura ^[14] que los grafos aleatorios son Ramanujan con una probabilidad sustancial (aproximadamente 52%). Además de la evidencia numérica directa, hay cierto respaldo teórico para esta conjetura: la brecha espectral de un grafo -regular parece comportarse de acuerdo con una distribución de Tracy-Widom de la teoría de matrices aleatorias, que predeciría la misma asintótica. ${\displaystyle d}$ ${\displaystyle \epsilon >0}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle \lambda (G)<2{\sqrt {d-1}}+\epsilon }$ ${\displaystyle d}$

Aplicaciones de los gráficos de Ramanujan

Los grafos expansores tienen muchas aplicaciones en la informática, la teoría de números y la teoría de grupos; véase, por ejemplo, la encuesta de Lubotzky sobre aplicaciones a las matemáticas puras y aplicadas y la encuesta de Hoory, Linial y Wigderson, que se centra en la informática. Los grafos de Ramanujan son, en cierto sentido, los mejores expansores, por lo que son especialmente útiles en aplicaciones en las que se necesitan expansores. Es importante destacar que los grafos de Lubotzky, Phillips y Sarnak se pueden recorrer con extrema rapidez en la práctica, por lo que son prácticos para las aplicaciones.

Algunas aplicaciones de ejemplo incluyen:

• En una aplicación a solucionadores rápidos para sistemas lineales laplacianos, Lee, Peng y Spielman ^[15] se basaron en la existencia de gráficos Ramanujan bipartitos de cada grado para aproximar rápidamente el gráfico completo.
• Lubetzky y Peres demostraron que el paseo aleatorio simple exhibe un fenómeno de corte en todos los grafos de Ramanujan. ^[16] Esto significa que el paseo aleatorio experimenta una transición de fase desde estar completamente sin mezclar a estar completamente mezclado en la norma de variación total. Este resultado depende en gran medida de que el grafo sea Ramanujan, no solo un expansor: se sabe que algunos buenos expansores no exhiben un fenómeno de corte. ^[17]
• Los gráficos de Ramanujan de Pizer se han propuesto como base para la criptografía de curva elíptica postcuántica . ^[18]
• Los gráficos de Ramanujan se pueden utilizar para construir códigos expansores , que son buenos códigos de corrección de errores .

Véase también

• Gráfico expansor
• Con destino a Alon-Boppana
• Lema de mezcla de expansores
• Teoría de grafos espectrales

Referencias

1. Artículo de investigación de M. Ram Murty
2. Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Gráficos de Ramanujan". Combinatorica . 8 (3): 261–277. doi :10.1007/BF02126799. S2CID  206812625.
3. Terras, Audrey (2011), Funciones zeta de gráficos: Un paseo por el jardín , Cambridge Studies in Advanced Mathematics, vol. 128, Cambridge University Press, ISBN 978-0-521-11367-0, Sr.  2768284
4. Weisstein, Eric W. "Gráfico icosaédrico". mathworld.wolfram.com . Consultado el 29 de noviembre de 2019 .
5. Li, Winnie (2020). "La conjetura de Ramanujan y sus aplicaciones". Philosophical Transactions of the Royal Society A . 378–2163 (2163). Código Bibliográfico :2020RSPTA.37880441W. doi :10.1098/rsta.2018.0441. PMC 6939229 . PMID  31813366. 
6. Margulis, GA (1988). "Construcciones explícitas de esquemas combinatorios en teoría de grupos y sus aplicaciones en la construcción de expansores y concentradores". Probl. Peredachi Inf . 24–1 : 51–60.
7. Moshe Morgenstern (1994). "Existencia y construcciones explícitas de gráficos regulares de Ramanujan q+1 para cada potencia prima q". Journal of Combinatorial Theory . Serie B. 62 : 44–62. doi : 10.1006/jctb.1994.1054 .
8. Pizer, Arnold K. (1990), "Gráficos de Ramanujan y operadores de Hecke", Boletín de la American Mathematical Society , Nueva serie, 23 (1): 127–137, doi : 10.1090/S0273-0979-1990-15918-X , MR  1027904
9. Adam Marcus ; Daniel Spielman ; Nikhil Srivastava (2013). Familias entrelazadas I: grafos Ramanujan bipartitos de todos los grados (PDF) . Fundamentos de la informática (FOCS), 54.º simposio anual del IEEE de 2013.
10. Adam Marcus ; Daniel Spielman ; Nikhil Srivastava (2015). Familias entrelazadas IV: gráficos Ramanujan bipartitos de todos los tamaños (PDF) . Fundamentos de la ciencia de la computación (FOCS), 56.º simposio anual del IEEE de 2015.
11. Michael B. Cohen (2016). Gráficos de Ramanujan en tiempo polinomial . Fundamentos de la informática (FOCS), 57.º simposio anual del IEEE de 2016. arXiv : 1604.03544 . doi :10.1109/FOCS.2016.37.
12. Hall, Chris; Puder, Doron; Sawin, William F. (2018). "Recubrimientos de grafos de Ramanujan". Avances en Matemáticas . 323 : 367–410. arXiv : 1506.02335 . doi :10.1016/j.aim.2017.10.042.
13. Friedman, Joel (2003). "Expansores relativos o grafos de Ramanujan débilmente relativos". Duke Mathematical Journal . 118 (1): 19–35. doi :10.1215/S0012-7094-03-11812-8. MR  1978881.
14. Miller, Steven J.; Novikoff, Tim; Sabelli, Anthony (2008). "La distribución de los mayores valores propios no triviales en familias de grafos regulares aleatorios". Experimental Mathematics . 17 (2): 231–244. arXiv : math/0611649 . doi :10.1080/10586458.2008.10129029.
15. Lee, Yin Tat; Peng, Richard; Spielman, Daniel A. (13 de agosto de 2015). "Solucionadores de Cholesky esparcidos para sistemas lineales SDD". arXiv : 1506.08204 [cs.DS].
16. Lubetzky, Eyal; Peres, Yuval (1 de julio de 2016). "Límite de corte en todos los grafos de Ramanujan". Análisis geométrico y funcional . 26 (4): 1190–1216. arXiv : 1507.04725 . doi :10.1007/s00039-016-0382-7. ISSN  1420-8970. S2CID  13803649.
17. Lubetzky, Eyal; Sly, Allan (1 de enero de 2011). "Expansores explícitos con fenómenos de corte". Revista electrónica de probabilidad . 16 (ninguno). arXiv : 1003.3515 . doi : 10.1214/EJP.v16-869 . ISSN  1083-6489. S2CID  9121682.
18. Eisenträger, Kirsten ; Hallgren, Sean; Lauter, Kristin ; Morrison, Travis; Petit, Christophe (2018), "Gráficos de isogenia supersingular y anillos de endomorfismo: reducciones y soluciones" (PDF) , en Nielsen, Jesper Buus; Rijmen, Vincent (eds.), Avances en criptología – EUROCRYPT 2018: 37.ª Conferencia internacional anual sobre la teoría y las aplicaciones de las técnicas criptográficas, Tel Aviv, Israel, 29 de abril - 3 de mayo de 2018, Actas, Parte III (PDF) , Lecture Notes in Computer Science, vol. 10822, Cham: Springer, págs. 329–368, doi :10.1007/978-3-319-78372-7_11, ISBN 978-3-319-78371-0, MR  3794837, S2CID  4850644

Lectura adicional

• Giuliana Davidoff ; Peter Sarnak ; Alain Valette (2003). Teoría elemental de números, teoría de grupos y grafos de Ramanujan . Textos para estudiantes de LMS. Vol. 55. Cambridge University Press . ISBN 0-521-53143-8.OCLC 50253269  .
• Sunada, Toshikazu (1986). " Funciones L en geometría y algunas aplicaciones". En Shiohama, Katsuhiro; Sakai, Takashi; Sunada, Toshikazu (eds.). Curvatura y topología de variedades de Riemann: Actas del 17.º Simposio Internacional Taniguchi celebrado en Katata, Japón, del 26 al 31 de agosto de 1985. Lecture Notes in Mathematics. Vol. 1201. Berlín: Springer. págs. 266–284. doi :10.1007/BFb0075662. ISBN . 978-3-540-16770-9.Sr. 0859591  .

Enlaces externos

• Documento de investigación de M. Ram Murty
• Documento de investigación de Alexander Lubotzky
• Artículo de investigación de Hoory, Linial y Wigderson