En la teoría de grafos espectrales , un grafo de Ramanujan es un gráfico regular cuya brecha espectral es casi tan grande como sea posible (ver teoría de grafos extremos ). Estos gráficos son excelentes expansores espectrales . Como señala el artículo de la encuesta de Murty , 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 el nombre indirecto 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
Dejar estar conectado -Gráfico regular con vértices y dejar ser los valores propios de la matriz de adyacencia de(o el espectro de). Porque está conectado y -regular, sus valores propios satisfacen .
Definir . Un conectado-Gráfico regular es un gráfico de Ramanujan si.
Muchas fuentes utilizan una definición alternativa (siempre que exista con ) para definir los gráficos de Ramanujan. [1] En otras palabras, permitimosademás de los valores propios "pequeños". Desdesi y solo si el gráfico es bipartito , nos referiremos a los gráficos que satisfacen esta definición alternativa pero no a los gráficos de Ramanujan bipartitos de primera definición .
Como lo observó Toshikazu Sunada , un gráfico regular es Ramanujan si y solo si su función Ihara zeta satisface un análogo de la hipótesis de Riemann . [2]
Ejemplos y construcciones
El gráfico completo tiene espectro , y por lo tanto y el gráfico es un gráfico de Ramanujan para cada . El gráfico bipartito completo tiene espectro y por tanto es un grafo Ramanujan bipartito para cada .
El gráfico de Petersen tiene espectro, por lo que es un gráfico Ramanujan regular de 3. El gráfico icosaédrico es un gráfico de Ramanujan regular de 5. [3]
Un gráfico de Paley de orden es -regular con todos los demás valores propios siendo , lo que hace que los gráficos de Paley sean una familia infinita de gráficos de Ramanujan.
Los matemáticos suelen estar interesados en construir -Gráficos Ramanujan regulares para cada fijo . Las construcciones actuales de familias infinitas de tales gráficos de Ramanujan son a menudo algebraicas.
- Lubotzky , Phillips y Sarnak [1] muestran cómo construir una familia infinita de-Gráficos Ramanujan regulares, siempre que es un número primo y. Su demostración utiliza la conjetura de Ramanujan , que llevó al nombre de los gráficos de Ramanujan. Además de ser gráficos de Ramanujan, su construcción satisface algunas otras propiedades, por ejemplo, su circunferencia es dónde es el número de nodos.
- Morgenstern [4] amplió la construcción de Lubotzky, Phillips y Sarnak. Su construcción extendida se mantiene siempre quees un poder primordial .
- Arnold Pizer demostró que los gráficos de isogenia supersingular son Ramanujan, aunque tienden a tener una circunferencia menor que los gráficos de Lubotzky, Phillips y Sarnak. [5] 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. Estos gráficos se han propuesto como base para la criptografía de curva elíptica postcuántica . [6]
- Adam Marcus , Daniel Spielman y Nikhil Srivastava [7] demostraron la existencia de infinitos-Gráficos Ramanujan bipartitos regulares para cualquier. Posteriormente [8] demostraron que existen grafos Ramanujan bipartitos de cada grado y cada número de vértices. Michael B. Cohen [9] mostró cómo construir estos gráficos en tiempo polinomial.
Sigue siendo un problema abierto si hay infinitas -Gráficos Ramanujan regulares (no bipartitos) para cualquier . En particular, el problema está abierto a, el caso más pequeño para el que no es un poder principal y, por lo tanto, no está cubierto por la construcción de Morgenstern.
Gráficos de Ramanujan como gráficos de expansión
El constante en la definición de los gráficos de Ramanujan es la mejor constante posible para cada y para gráficos grandes: en otras palabras, para cada y , existe tal que todos -Gráficos regulares con al menos los vértices satisfacen . (Ver más abajo para enunciados más precisos y bosquejos de prueba.) Por otro lado, Friedman [10] mostró que para cada y y para lo suficientemente grande , Cualquiera -regular -Gráfico de vértice satisface con alta probabilidad. Esto significa que los gráficos de Ramanujan son esencialmente los mejores gráficos de expansión posibles .
Debido a lograr el límite apretado en , el lema de mezcla del expansor da excelentes límites 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 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á acotado logarítmicamente en términos del número de vértices.
Extremalidad de los gráficos de Ramanujan
Si es un -Gráfica regular con diámetro , un teorema debido a Noga Alon [11] establece
Cuando sea es -regular y conectado en al menos tres vértices, , y por lo tanto . Dejar ser el conjunto de todos los conectados -Gráficos regulares con al menos vértices. Debido a que el diámetro mínimo de los gráficos en se acerca al infinito para fijo y aumentando , este teorema implica un teorema anterior de Alon y Boppana [12] que establece
Un límite ligeramente más fuerte es
dónde . El esquema de la prueba es el siguiente. Llevar. Dejar ser el completo -arbol de altura (cada vértice interno tiene niños), y dejar ser su matriz de adyacencia. Queremos demostrar que, dónde . Definir una función por , dónde es la distancia desde a la raíz de . Se puede verificar que y eso es de hecho el valor propio más grande de . Ahora deja y ser un par de vértices a distancia en y definir
dónde es un vértice en cuya distancia a la raíz es igual a la distancia desde a y el simétrico para . (Uno puede pensar en esto como "incrustar" dos copias disjuntas de, con algunos vértices colapsados en uno.) Al elegir el valor de reales positivos apropiadamente obtenemos , por cerca de y por cerca de . Entonces, por el teorema mínimo-máximo obtenemos
Ver también
- Gráfico expansor
- Lema de mezcla de expansor
- Teoría de grafos espectrales
Referencias
- ↑ a b Alexander Lubotzky; Ralph Phillips; Peter Sarnak (1988). "Gráficos de Ramanujan". Combinatorica . 8 (3): 261-277. doi : 10.1007 / BF02126799 . S2CID 206812625 .
- ^ Terras, Audrey (2011), Zeta functions of graphs: A walk through the garden , Cambridge Studies in Advanced Mathematics, 128 , Cambridge University Press, ISBN 978-0-521-11367-0, MR 2768284
- ^ Weisstein, Eric W. "Gráfico icosaédrico" . mathworld.wolfram.com . Consultado el 29 de noviembre de 2019 .
- ^ Moshe Morgenstern (1994). "Existencia y construcciones explícitas de q + 1 gráficos Ramanujan regulares para cada potencia prima q". Revista de Teoría Combinatoria, Serie B . 62 : 44–62. doi : 10.1006 / jctb.1994.1054 .
- ^ Pizer, Arnold K. (1990), "Gráficos de Ramanujan y operadores de Hecke", Bulletin of the American Mathematical Society , New Series, 23 (1): 127-137, doi : 10.1090 / S0273-0979-1990-15918-X , Señor 1027904
- ^ 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.), Advances in Cryptology - EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 29 de abril - 3 de mayo de 2018, Actas, Parte III (PDF) , Conferencia Notes in Computer Science, 10822 , Cham: Springer, págs. 329–368, doi : 10.1007 / 978-3-319-78372-7_11 , MR 3794837
- ^ Adam Marcus ; Daniel Spielman ; Nikhil Srivastava (2013). Familias entrelazadas I: Grafos Ramanujan bipartitos de todos los grados . Fundamentos de la informática (FOCS), 54º Simposio Anual del IEEE 2013.
- ^ Adam Marcus ; Daniel Spielman ; Nikhil Srivastava (2015). Familias entrelazadas IV: Gráficos Ramanujan bipartitos de todos los tamaños . Fundamentos de la informática (FOCS), 56º Simposio Anual del IEEE 2015.
- ^ Michael B. Cohen (2016). Gráficos de Ramanujan en tiempo polinomial . Fundamentos de la informática (FOCS), 57º Simposio Anual del IEEE 2016. arXiv : 1604.03544 . doi : 10.1109 / FOCS.2016.37 .
- ^ Friedman, Joel (2003). "Expansores relativos o gráficos de Ramanujan débilmente relativamente". Duke Math. J . 118 (1): 19–35. doi : 10.1215 / S0012-7094-03-11812-8 . Señor 1978881 .
- ^ Nilli, A. (1991), "Sobre el segundo valor propio de un gráfico", Matemáticas discretas , 91 (2): 207-210, doi : 10.1016 / 0012-365X (91) 90112-F , MR 1124768.
- ^ Alon, N. (1986). "Autovalores y expansores". Combinatorica . 6 (2): 83–96. doi : 10.1007 / BF02579166 . Señor 0875835 . S2CID 41083612 .
Otras lecturas
- Giuliana Davidoff ; Peter Sarnak ; Alain Valette (2003). Teoría elemental de números, teoría de grupos y grafos de Ramanujan . Textos de estudiantes de LMS. 55 . Prensa de la Universidad de Cambridge . ISBN 0-521-53143-8. OCLC 50253269 .
- T. Sunada (1985). "Funciones L en geometría y algunas aplicaciones". Notas de clase en matemáticas . Apuntes de clase en matemáticas. 1201 : 266-284. doi : 10.1007 / BFb0075662 . ISBN 978-3-540-16770-9.
enlaces externos
- Documento de encuesta de M. Ram Murty