gráfico de ramanujan

En el campo matemático de la teoría de grafos espectrales , un gráfico de Ramanujan es un gráfico regular cuyo espacio espectral es casi lo más grande posible (ver teoría de grafos extremos ). Estos gráficos son excelentes expansores espectrales . Como señala el artículo de Murty ^[1] , los gráficos 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 gráficos llevan indirectamente el nombre de Srinivasa Ramanujan ; su nombre proviene de la conjetura de Ramanujan-Petersson , que se utilizó en la construcción de algunos de estos gráficos.

Definición

Sea un gráfico regular conectado con vértices y sean los valores propios de la matriz de adyacencia de (o el 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 conectado 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 ) para definir los gráficos de Ramanujan. ^[2] En otras palabras, permitimos además de los valores propios "pequeños". Dado que si y sólo si el gráfico es bipartito , nos referiremos a los gráficos que satisfacen esta definición alternativa pero no a la primera definición de gráficos bipartitos de Ramanujan . Si es un gráfico de Ramanujan, entonces es un gráfico de Ramanujan bipartito, por lo que la existencia de gráficos 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 Ihara zeta 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 espectro , por lo que es un gráfico de Ramanujan de 3 regulares. El gráfico icosaédrico es un gráfico de Ramanujan de 5 regulares. ^[4] ${\displaystyle 3,1,1,1,1,1,-2,-2,-2,-2}$
• Un gráfico de orden de Paley es regular y todos los demás valores propios son , lo que hace que los gráficos de Paley sean una familia infinita de gráficos de Ramanujan. ${\displaystyle q}$ ${\displaystyle {\frac {q-1}{2}}}$ ${\displaystyle {\frac {-1\pm {\sqrt {q}}}{2}}}$
• De manera más general, sea un polinomio de grado 2 o 3 sobre . Sea la imagen de un conjunto múltiple y supongamos . Entonces el gráfico de Cayley 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 gráficos de Ramanujan regulares para cada elemento fijo . Estas familias son útiles en aplicaciones. ${\displaystyle d}$ ${\displaystyle d}$

Construcciones algebraicas

Varias construcciones explícitas de gráficos de Ramanujan surgen como gráficos 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] mostraron cómo construir una familia infinita de gráficos regulares de Ramanujan, siempre que sea un número primo y . Ambas pruebas utilizan la conjetura de Ramanujan , lo que dio lugar al nombre de gráficos de Ramanujan. Además de ser gráficos de Ramanujan, estas construcciones satisfacen algunas otras propiedades, por ejemplo, su circunferencia es donde está el número de nodos. ${\displaystyle (p+1)}$ ${\displaystyle p}$ ${\displaystyle p\equiv 1{\pmod {4}}}$ ${\displaystyle \Omega (\log _{p}(n))}$ ${\displaystyle n}$

Esbocemos la construcción Lubotzky-Phillips-Sarnak. Sea un primo no igual a . Según el teorema de los cuatro cuadrados de Jacobi , hay soluciones a la ecuación donde es par y es impar. A cada una de estas soluciones asocie la matriz ${\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] amplió posteriormente la construcción de Lubotzky, Phillips y Sarnak. Su construcción ampliada se mantiene siempre que sea una potencia primordial . ${\displaystyle p}$

Arnold Pizer demostró que las gráficas de isogenia supersingulares son Ramanujan, aunque tienden a tener menor circunferencia que las gráficas de Lubotzky, Phillips y Sarnak. ^[8] Al igual que las gráficas de Lubotzky, Phillips y Sarnak, los grados de estas gráficas 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 gráficos de Ramanujan bipartitos regulares para cualquier . Posteriormente ^[10] demostraron que existen gráficos bipartitos de Ramanujan de cada grado y de cada número de vértices. Michael B. Cohen ^[11] mostró cómo construir estos gráficos en tiempo polinomial. ${\displaystyle d}$ ${\displaystyle d\geq 3}$

El trabajo inicial siguió un planteamiento de Bilu y Linial . Consideraron una operación llamada 2-lift que toma un gráfico regular con vértices y un signo en cada arista, y produce un nuevo gráfico regular en los vértices. Bilu y Linial conjeturaron que siempre existe una firma para que cada nuevo valor propio de tenga magnitud como máximo . Esta conjetura garantiza la existencia de gráficos de Ramanujan con grados y vértices para cualquiera ; simplemente comience con el gráfico completo y, de forma iterativa, realice 2 elevaciones 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 se cumple cuando ya es un gráfico bipartito de Ramanujan, lo cual es suficiente para concluir el resultado de existencia. La secuela ^[10] demostró la afirmación más contundente de que una suma de coincidencias bipartitas aleatorias es Ramanujan con una probabilidad que no desaparece. Hall, Puder y Sawin ^[12] ampliaron el trabajo original de Marcus, Spielman y Srivastava a los ascensores r . ${\displaystyle G}$ ${\displaystyle d}$

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

Gráficos de Ramanujan como gráficos de expansión

La constante en la definición de los gráficos de Ramanujan es asintóticamente nítida. Más precisamente, el límite de Alon-Boppana establece que para cada y , existen gráficos todos regulares con al menos vértices que satisfacen . Esto significa que los gráficos de Ramanujan son esencialmente los mejores gráficos de expansión 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 lograr el límite estrecho de , el lema de mezcla del expansor proporciona límites excelentes en la uniformidad de la distribución de los bordes en los gráficos de Ramanujan, y cualquier recorrido aleatorio en los gráficos tiene un tiempo de mezcla logarítmico (en términos del número de vértices): en otras palabras, el paseo aleatorio converge muy rápidamente a la distribución estacionaria (uniforme). Por lo tanto, el diámetro de los gráficos 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] demostró que muchas familias de gráficos aleatorios son débilmente Ramanujan . Esto significa que para cada y y para un tamaño suficientemente grande , un gráfico de vértice regular aleatorio satisface con alta probabilidad. Si bien este resultado muestra que los gráficos aleatorios están cerca de ser Ramanujan, no se puede utilizar para probar la existencia de gráficos de Ramanujan. Sin embargo, se conjetura ^[14] que los gráficos aleatorios son Ramanujan con una probabilidad sustancial (aproximadamente 52%). Además de la evidencia numérica directa, existe cierto apoyo teórico para esta conjetura: la brecha espectral de un gráfico 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 gráficos de expansión tienen muchas aplicaciones a la informática, la teoría de números y la teoría de grupos; consulte, 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 gráficos de Ramanujan son, en cierto sentido, los mejores. expansores, por lo que son especialmente útiles en aplicaciones donde se necesitan expansores. Es importante destacar que los gráficos de Lubotzky, Phillips y Sarnak se pueden recorrer extremadamente rápido 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 bipartitos de Ramanujan de cada grado para aproximarse rápidamente al gráfico completo.
• Lubetzky y Peres demostraron que el paseo aleatorio simple presenta un fenómeno de corte en todos los gráficos de Ramanujan. ^[16] Esto significa que el paseo aleatorio sufre una transición de fase desde estar completamente sin mezclar hasta completamente mezclado en la norma de variación total. Este resultado depende en gran medida de que el gráfico sea Ramanujan, no solo un expansor; se sabe que algunos buenos expansores no presentan corte. ^[17]
• Los gráficos de Ramanujan de Pizer se han propuesto como base para la criptografía de curva elíptica poscuántica . ^[18]
• Los gráficos de Ramanujan se pueden utilizar para construir códigos de expansión , que son buenos códigos de corrección de errores .

Ver también

• Gráfico de expansión
• Alon-Boppana obligado
• Lema de mezcla del expansor
• Teoría de grafos espectrales

Referencias

1. Documento de encuesta de M. Ram Murty
2. Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Gráficos de Ramanujan". Combinatoria . 8 (3): 261–277. doi :10.1007/BF02126799. S2CID  206812625.
3. Terras, Audrey (2011), Funciones Zeta de gráficas: un paseo por el jardín , Estudios de Cambridge en Matemáticas Avanzadas, vol. 128, Prensa de la Universidad de Cambridge, ISBN 978-0-521-11367-0, señor  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". Transacciones filosóficas de la Royal Society A. 378–2163 (2163). Código Bib : 2020RSPTA.37880441W. doi :10.1098/rsta.2018.0441. PMC 6939229 . PMID  31813366. 
6. Margulis, GA (1988). "Construcciones explícitas de teoría de grupos de esquemas combinatorios y sus aplicaciones en la construcción de expansores y concentradores". Problema. Peredachi Inf . 24–1 : 51–60.
7. Moshe Morgenstern (1994). "Existencia y construcciones explícitas de q + 1 gráficos regulares de Ramanujan para cada potencia principal q". Revista de teoría combinatoria . 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 Sociedad Estadounidense de Matemáticas , Nueva serie, 23 (1): 127–137, doi : 10.1090/S0273-0979-1990-15918-X , señor  1027904
9. Adam Marcus ; Daniel Spielman ; Nikhil Srivastava (2013). Familias entrelazadas I: gráficos bipartitos de Ramanujan de todos los grados (PDF) . Fundamentos de las Ciencias de la Computación (FOCS), 54º Simposio Anual del IEEE 2013.
10. Adam Marcus ; Daniel Spielman ; Nikhil Srivastava (2015). Familias entrelazadas IV: gráficos bipartitos de Ramanujan de todos los tamaños (PDF) . Fundamentos de las Ciencias de la Computación (FOCS), 56º Simposio Anual del IEEE 2015.
11. Michael B. Cohen (2016). Gráficos de Ramanujan en tiempo polinomial . Fundamentos de las Ciencias de la Computación (FOCS), 57º Simposio Anual del IEEE de 2016. arXiv : 1604.03544 . doi :10.1109/FOCS.2016.37.
12. Salón, Chris; Puder, Doron; Sawin, William F. (2018). "Revestimientos de gráficos 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 gráficos relativamente débiles de Ramanujan". Revista de Matemáticas de Duke . 118 (1): 19–35. doi :10.1215/S0012-7094-03-11812-8. SEÑOR  1978881.
14. Molinero, Steven J.; Novikoff, Tim; Sabelli, Antonio (2008). "La distribución de los valores propios no triviales más grandes en familias de gráficos regulares aleatorios". Matemáticas Experimentales . 17 (2): 231–244. arXiv : matemáticas/0611649 . doi :10.1080/10586458.2008.10129029.
15. Lee, Yin Tat; Peng, Richard; Spielman, Daniel A. (13 de agosto de 2015). "Solucionadores Cholesky dispersos para sistemas lineales SDD". arXiv : 1506.08204 [cs.DS].
16. Lubetzky, Eyal; Peres, Yuval (1 de julio de 2016). "Límite en todos los gráficos 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; Astuto, 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.a Conferencia internacional anual sobre la teoría y aplicaciones de técnicas criptográficas, Tel Aviv, Israel, 29 de abril - 3 de mayo de 2018, Actas, Parte III ( PDF) , Conferencia Notas en Ciencias de la Computación, vol. 10822, Cham: Springer, págs. 329–368, doi :10.1007/978-3-319-78372-7_11, ISBN 978-3-319-78371-0, SEÑOR  3794837, S2CID  4850644

Otras lecturas

• Giuliana Davidoff ; Pedro Sarnak ; Alain Valette (2003). Teoría elemental de números, teoría de grupos y gráficos de Ramanujan . Textos para estudiantes de LMS. vol. 55. Prensa de la Universidad de Cambridge . ISBN 0-521-53143-8. OCLC  50253269.
• Sunada, Toshikazu (1986). " L -funciones 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 . Apuntes de conferencias de matemáticas. vol. 1201. Berlín: Springer. págs. 266–284. doi :10.1007/BFb0075662. ISBN 978-3-540-16770-9. SEÑOR  0859591.

enlaces externos

• Documento de encuesta de M. Ram Murty
• Documento de encuesta de Alexander Lubotzky
• Documento de encuesta de Hoory, Linial y Wigderson