Para un $d$ -regular, donde $d$ puede ser fijo o crecer lentamente con el tamaño del gráfico $n$ ¿Qué podemos decir de su espectro? ¿Cree que tiene un espectro simple?
Gracias, señor,
Respuestas
¿Demasiados anuncios?
Peter
Puntos
1681
En 1986, Noga Alon conjeturó en un Combinatoria artículo que, para cualquier grado $d \ge 3$ y para cualquier $\epsilon > 0$ , más $d$ -gráficos regulares en $n$ los vértices tienen todos sus valores propios excepto $\lambda_1=d$ acotado anteriormente por $2 \sqrt{d−1} + \epsilon$ . En 2003, Joel Friedman estableció esta conjetura: " Demostración de la conjetura del segundo valor propio de Alon ," 2003. En un artículo de Miller, Novikoff y A. A. se describen algunos avances sobre la distribución de los valores propios. en un artículo de Miller, Novikoff y Anthony Sabelli, "La distribución de los mayores valores propios no triviales en familias de grafos regulares aleatorios" en Matemáticas experimentales , 2008 . Quizás algunas de estas referencias le ayuden.
Fernando Briano
Puntos
3704
Sí, creo que tendrá espectro simple para d >= 3 y me parece algo que debería haberse demostrado, aunque no lo encuentro.
Existe una asociación poco clara entre los automorfismos de un grafo y los valores propios múltiples, y como la mayoría de los grafos regulares tienen un grupo de automorfismos trivial, perdemos esta fuente de valores propios múltiples. No hay otras "razones" (frecuentes) para que un grafo tenga múltiples valores propios, por lo que en general no los tendrá.
AÑADIDO:
Estos son algunos números exactos para grafos cúbicos conectados (no isomorfos por pares): los grafos desconectados desaparecen numéricamente, por lo que podemos ignorarlos.
10 vértices - 19 grafos - 6 sin eigs repetidos = 31% simple
12 vértices - 85 grafos - 18 sin eigs repetidos = 21% simples
14 vértices - 509 grafos - 316 sin eigs repetidos = 62% simple
16 vértices - 4060 grafos - 2181 sin eigs repetidos = 54% simple
18 vértices - 41301 grafos - 26446 sin eigs repetidos = 64% simple
(En realidad esto está creciendo más lentamente de lo que esperaba... )
Matthew
Puntos
111
Supuse que no, pero Gordon me ha hecho cambiar de opinión para un grado superior a 2.
Si tiene grado 2 es una unión de ciclos. Los valores propios son $2\cos(\frac{2 \pi j}{k})$ para varios $ k$ . En particular 2 tiene multiplicidad el número de componentes.
Para grafos regulares aleatorios de grado superior a 2, yo diría que el comportamiento de los valores propios es como el de una matriz simétrica aleatoria grande. Esto ha sido bien estudiado, pero no por mí, todo lo que sé es la frase "Gaussian Orthogonal Ensemble".
Algunos experimentos con grafos de grado 3 sugieren que con 30 vértices es muy probable que haya un componente y un valor propio repetido (casi siempre 0) aproximadamente el 2% de las veces. Con 60 vértices es más bien el 0,2%.
Mystica555
Puntos
21
Publico esta respuesta para proporcionar algunas referencias e información adicionales sobre el espectro de la matriz de adyacencia. (Creo que con probabilidad $1$ los valores propios serán simples)
Ley de McKay [1] al azar $d$ -de los grafos regulares establece que el espectro converge débilmente al espectro de la cubierta universal del grafo, que es un $d$ -árbol regular en este caso. La medida espectral viene dada por $$d\mu_{\text{McKay}}(x)=d\mu(x)=\begin{cases} \frac{d\sqrt{4(d-1)-x^{2}}}{2\pi(d^{2}-x^{2})}dx & |x|\leq2\sqrt{d-1}\\ 0 & |x|>2\sqrt{d-1} \end{cases}. $$
En otras palabras, si tomamos un $d$ -grafo regular $G_n$ con matriz de adyacencia $A_n$ y los valores propios $\lambda_n\leq \dots \leq \lambda_1=d$ entonces para cada $-2\sqrt{d-1}\leq a<b\leq 2\sqrt{d-1}$ tenemos
$$\frac{\#\left\{ \lambda_{i}:\ a\leq\lambda_{i}\leq b\right\} }{n}=\int_{a}^{b}d\mu_{McKay}(x)+o_{n}(1)$$ con probabilidad de ir a $1$ como $n\rightarrow \infty$ .
Tran Vu y Wang [2] demostró que si $d\rightarrow\infty$ a medida que el tamaño del grafo llega a infinito, el espectro converge a Ley del semicírculo de Wigner . Obsérvese que para un grado fijo bajo no obtenemos el semicírculo - esto se debe a que el $2k^{th}$ momentos no son simplemente los $k^{th}$ Número catalán multiplicado por el radio espectral a la potencia de $2k$ - el punto base tiene grado $d$ y esto afecta al cálculo cuando $\frac{d}{d-1}\neq 1+o(1)$ .
Para una breve descripción de estos resultados junto con más referencias, recomiendo la nota de Yufei Zhao Distribuciones espectrales de grafos aleatorios
Referencias:
[1] Brendan Mckay, 1981, La distribución de valores propios esperada de un grafo regular grande .
[2] Linh Tran, Van Vu, Ke Wang, 2010 Grafos aleatorios dispersos: Valores y vectores propios .
Zach Blumenstein
Puntos
26
