Teoría elemental de números, teoría de grupos y grafos de Ramanujan es un libro de matemáticas cuyo objetivo es hacer accesible la construcción de grafos de Ramanujan a los estudiantes de matemáticas de nivel universitario. Para ello, cubre varios otros temas importantes en teoría de grafos , teoría de números y teoría de grupos . Fue escrito por Giuliana Davidoff , Peter Sarnak y Alain Valette, y publicado en 2003 por Cambridge University Press , como volumen 55 de la serie de libros de textos para estudiantes de la London Mathematical Society.
En teoría de grafos , los grafos expansores son grafos no dirigidos con alta conectividad: cada subconjunto de vértices lo suficientemente pequeño tiene muchas aristas que lo conectan con las partes restantes del grafo. Los grafos expansores dispersos tienen muchas aplicaciones importantes en informática, incluido el desarrollo de códigos de corrección de errores , el diseño de redes de ordenamiento y la desaleatorización de algoritmos aleatorios . Para estas aplicaciones, el grafo debe construirse explícitamente, en lugar de simplemente probar su existencia. [1] [2]
Una forma de demostrar que un grafo es un expansor es estudiar los valores propios de su matriz de adyacencia . Para un grafo - regular , estos son números reales en el intervalo , y el valor propio más grande (que corresponde al vector propio de todos los 1 ) es exactamente . La expansión espectral del grafo se define a partir de la diferencia entre el valor propio más grande y el segundo más grande, la brecha espectral , que controla la rapidez con la que un paseo aleatorio en el grafo se establece en su distribución estable ; esta brecha puede ser como máximo . Los grafos de Ramanujan se definen como los grafos que son óptimos desde el punto de vista de la expansión espectral: son grafos -regulares cuya brecha espectral es exactamente . [3]
Aunque los grafos de Ramanujan con alto grado , como los grafos completos , son fáciles de construir, se necesitan grafos expansores de bajo grado para las aplicaciones de estos grafos. Actualmente se conocen varias construcciones de grafos de Ramanujan de bajo grado, las primeras de las cuales fueron realizadas por Lubotzky, Phillips y Sarnak (1988) y Margulis (1988). [3] [4] [5] El revisor Jürgen Elstrod escribe que "si bien la descripción de estos grafos es elemental, la prueba de que tienen las propiedades deseadas no lo es". La teoría elemental de números, la teoría de grupos y los grafos de Ramanujan tienen como objetivo hacer que la mayor parte posible de esta teoría sea accesible a un nivel elemental . [3]
Sus autores han dividido la Teoría de Números Elementales, la Teoría de Grupos y los Grafos de Ramanujan en cuatro capítulos. El primero de ellos proporciona los antecedentes de la teoría de grafos , incluyendo material sobre la circunferencia de los grafos (la longitud del ciclo más corto), sobre la coloración de los grafos y sobre el uso del método probabilístico para demostrar la existencia de grafos para los que tanto la circunferencia como el número de colores necesarios son grandes. Esto proporciona una motivación adicional para la construcción de grafos de Ramanujan, ya que los construidos en el libro proporcionan ejemplos explícitos del mismo fenómeno. Este capítulo también proporciona el material esperado sobre la teoría de grafos espectrales , necesario para la definición de los grafos de Ramanujan. [2] [3] [6]
El capítulo 2, sobre teoría de números , incluye el teorema de la suma de dos cuadrados que caracteriza a los números enteros positivos que pueden representarse como sumas de dos cuadrados de números enteros (estrechamente relacionado con las normas de los números enteros gaussianos ), el teorema de los cuatro cuadrados de Lagrange según el cual todos los números enteros positivos pueden representarse como sumas de cuatro cuadrados (probado utilizando las normas de los cuaterniones de Hurwitz ), y la reciprocidad cuadrática . El capítulo 3 trata de la teoría de grupos , y en particular de la teoría de los grupos lineales especiales proyectivos y de los grupos lineales proyectivos sobre los cuerpos finitos cuyo orden es un número primo , y de la teoría de la representación de grupos finitos . [3] [6]
El capítulo final construye el grafo de Ramanujan para dos números primos y como un grafo de Cayley del grupo o (dependiendo de la reciprocidad cuadrática) con generadores definidos tomando módulo un conjunto de cuaterniones provenientes de representaciones de como una suma de cuatro cuadrados. Estos grafos son automáticamente -regulares. El capítulo proporciona fórmulas para sus números de vértices y estimaciones de su circunferencia. Si bien no prueba completamente que estos grafos sean grafos de Ramanujan, el capítulo prueba que son expansores espectrales y describe cómo la afirmación de que son grafos de Ramanujan se desprende de la prueba de Pierre Deligne de la conjetura de Ramanujan (la conexión con Ramanujan de la que se derivó el nombre de estos grafos). [3] [6]
Este libro está destinado a estudiantes universitarios avanzados que ya han visto algo de álgebra abstracta y análisis real . El revisor Thomas Shemanske sugiere usarlo como base para un seminario de último año, como un camino rápido hacia muchos temas importantes y un ejemplo interesante de cómo estos temas aparentemente separados unen fuerzas en esta aplicación. [6] Por otro lado, Thomas Pfaff piensa que sería difícil incluso para la mayoría de los estudiantes universitarios de último año, pero podría ser una buena opción para el estudio independiente o un curso electivo de posgrado. [2]
![{\estilo de visualización [-r,r]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5dbcf3f99b353b618465500fe9576e0850885ffd)
