Grafo de Ramanujan

Tales grafos son excelentes expansores espectrales.además de los valores propios "pequeños".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.y por lo tanto, es un grafo bipartito de Ramanujan para cadaLos matemáticos a menudo están interesados en construir grafos de RamanujanSigue siendo un problema abierto si hay infinitos grafos de RamanujanEn particular, el problema está abierto parano es una potencia prima y, por lo tanto, no está cubierto por la construcción de Morgenstern.Esto significa que los grafos de Ramanujan son esencialmente los mejores grafos expansores posibles.Cuando se necesita obtener un límite ajustado en, 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., un teorema debido a Noga Alon establece que[11]​ Cuando-regular y está conectado en al menos tres vértices,el conjunto de todos los grafos conectadosDado que el diámetro mínimo de los grafos ense acerca al infinito para, este teorema implica un teorema anterior de Alon y Boppana[12]​ que establece que Un límite ligeramente más fuerte es donde{\displaystyle g:V(T_{d,k})\rightarrow \mathbb {R} }un par de vértices a distanciaSe puede pensar en esto como "incrustar" dos copias disjuntas deAl elegir el valor de los reales positivos{\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),}Esto implica que se trata de un grafo 3-regular, formado por 18 vértices.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, que cumplen con la propiedad de que: Para ello, se ha utilizado el programa "MATLAB", diseñado para trabajar con matrices.equivale a resolver un polinomio de grado 18, calculando sus 18 raíces.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.