¿Cuáles son los teoremas o propiedades importantes de los valores propios de la matriz de adyacencia para un gráfico?

Answer 1

• El valor propio superior [matemática] \ lambda_1 [/ matemática] de la matriz de adyacencia se conoce como umbral epidémico, vea este artículo La propagación de epidemias en redes reales: un punto de vista de valor propio.
• He usado en el pasado un número constante de valores propios superiores de la matriz de adyacencia para contar triángulos rápidamente, vea esta página de papel en cmu.edu. Debido a las propiedades espectrales especiales de las redes del mundo real, esto reduce empíricamente un problema de multiplicación matriz-matriz a la realización de unos pocos números de multiplicación vectorial de matriz. Para obtener más información sobre estas propiedades especiales, consulte esta página de papel en sc.edu.

Como señala Richard Peng, es más común observar las matrices laplacianas. Un libro que contiene una gran cantidad de información tanto sobre laplacianos como sobre matrices de adyacencia es este Graph Spectra for Complex Networks – edición Kindle de Piet Van Mieghem. EBooks profesionales y técnicos de Kindle en Amazon.com.

Answer 2

Sea [math] G [/ math] una gráfica simple no dirigida de vértices [math] n [/ math] con matriz de adyacencia [math] A \ subseteq \ mathbb {R} ^ {n \ times n} [/ math].

1. Si [math] G [/ math] tiene un diámetro [math] d [/ math], entonces [math] A [/ math] tiene al menos [math] d + 1 [/ math] valores propios distintos.
2. Digamos que la gráfica es [matemática] k [/ matemática] -regular. Entonces [math] G [/ math] es bipartito si y solo si [math] -k [/ math] es un valor propio de [math] A [/ math].
3. Sea [math] t [/ math] el número de triángulos en [math] G [/ math]. Entonces [matemáticas] tr ~ A ^ 3 = 6t [/ matemáticas].
4. Si [math] G [/ math] es un gráfico lineal, entonces su valor propio mínimo es mayor o igual que [math] -2 [/ math].
5. Si [math] G [/ math] es [math] k [/ math] -regular con el menor valor propio [math] \ lambda [/ math], entonces [math] \ alpha (G) \ leq -n \ lambda / ( k – \ lambda) [/ math], donde [math] \ alpha (G) [/ math] es el tamaño del conjunto independiente más grande en [math] G [/ math].
6. Expansor de lema de mezcla.

Algunas referencias:

• Espectros de gráficos de Brouwer y Haemers
• Métodos de autovaloración de David Ellis

Answer 3

Por lo general, para valores propios, es más fácil observar la matriz laplaciana normalizada, que es la matriz de adyacencia normalizada por grados y sustraída de la matriz de identidad. Muchos teoremas suponen que la gráfica es d-regular porque en tales casos, estas dos matrices están más directamente asociadas.

Para la matriz de adyacencia de un gráfico d-regular no ponderado, las siguientes propiedades suelen ser bastante útiles:

1. Hay n valores propios reales.

2. Suponiendo que no haya bucles automáticos, estos valores propios suman 0, la traza de la matriz.

3. Los cuadrados de estos valores propios suman la norma Frobenius de la matriz, que a su vez es igual al número de aristas, 2dn.

4. Todos los valores propios están entre -d y d.

5. Si todos los valores propios están delimitados por d, por ejemplo, entre -0.9d y 0.9, el gráfico está muy bien conectado. Esto significa que no hay cuellos de botella en el gráfico, o que una caminata aleatoria se acercará rápidamente a la distribución uniforme. Los gráficos con esta propiedad se conocen como gráficos de expansión.

La imagen se vuelve mucho más complicada para gráficos dirigidos. En ese contexto, el teorema de Perron-Frobenius es probablemente un buen lugar para comenzar.

Answer 4

Aquí hay algunos hechos posiblemente interesantes / importantes sobre los espectros de gráficos simples que conozco actualmente:

• Un par de gráficos de distancia regular son cospectrales si y solo si tienen la misma matriz de intersección.
• Un par de gráficos regulares son cospectrales si y solo si sus complementos son cospectrales.
• El espectro de un gráfico de Cayley de un grupo abeliano finito está dado por una expresión en términos de los caracteres irreducibles de dicho grupo sobre [math] \ mathbb {C} [/ math] y la conexión establecida en contexto.
• La derivada formal de un polinomio característico de un gráfico simple [matemática] G [/ matemática] es igual a la suma de los polinomios característicos de sus subgrafías eliminadas por vértices, es decir, [matemática] \ phi ^ {‘} _ {G} ( x) = \ sum \ limits_ {u \ en V (G)} \ phi_ {Gu} (x) [/ math].
• Algunas familias posiblemente interesantes de gráficos de caminata regular que existen debido a la cantidad de valores propios distintos que tienen sus matrices de adyacencia:

• Cada gráfico conectado regular con a lo sumo cuatro valores propios distintos es walk-regular.
• Cada gráfico conectado libre de triángulos regular con a lo sumo seis valores propios distintos es regular a pie.

Hay un límite de valor propio mínimo en el número de independencia de un gráfico regular, llamado límite de Hoffman-Delsarte.

Además, un ejemplo de casos en los que los valores propios concretos reales de los gráficos son posiblemente interesantes son los casos en que ciertos gráficos se caracterizan por sus espectros, es decir, casos en los que ciertos gráficos tienen matrices de adyacencia cospectral si y solo si son isomorfos. Siempre es el caso de que los gráficos isomórficos tienen matrices de adyacencia cospectral, pero lo contrario no es cierto en general. Sin embargo, algunos gráficos se caracterizan de hecho por sus espectros concretos, y esos casos son posiblemente interesantes de identificar; Encontrar declaraciones más abstractas que sean verdaderas sobre cuándo exactamente los gráficos se caracterizan por sus espectros es un problema general interesante en mi opinión. Algunos primeros ejemplos de familias de gráficos que se caracterizan por sus espectros son los gráficos completos y los gráficos de estrellas.

Answer 5

Aquí hay algunas propiedades más de los valores propios de la matriz de adyacencia. Voy a suponer que los valores propios de la matriz de adyacencia son [math] \ lambda_1, \ ldots, \ lambda_n [/ math] (con posibles repeticiones). Además, los valores propios de un gráfico son los valores propios de su matriz de adyacencia.

1. Para cualquier número entero [math] k \ geq 0 [/ math], la suma [math] \ displaystyle \ sum_ {i = 0} ^ n {\ lambda_i} ^ k [/ math] es igual al número de pasos cerrados de longitud [matemática] k [/ matemática] en el gráfico. En particular:

1. Para [matemática] n = 0 [/ matemática], esto implica que la gráfica tiene vértices [matemática] n [/ matemática].
2. Para [matemáticas] n = 1 [/ matemáticas], esto implica que los valores propios suman cero.
3. Para [matemática] n = 2 [/ matemática], esto implica que el gráfico tiene [matemática] \ displaystyle \ frac {1} {2} \ sum_ {i = 0} ^ n {\ lambda_i} ^ 2 [/ matemática] bordes Corolario: un gráfico no tiene aristas si y solo si todos sus valores propios son cero.
4. Para [matemática] n = 3 [/ matemática], esto implica que el gráfico tiene [matemática] \ displaystyle \ frac {1} {6} \ sum_ {i = 0} ^ n {\ lambda_i} ^ 3 [/ matemática] triángulos (ciclos de tamaño 3). Corolario: un gráfico no tiene triángulos si y solo si esta cantidad es cero.
5. Para gráficos bipartitos, [math] \ sum_ {i = 0} ^ n {\ lambda_i} ^ k = 0 [/ math] para todos los [math] k [/ math] impares.

La suma de los valores absolutos de los valores propios es la energía del gráfico . Esto está relacionado con la química; de hecho, una de las primeras aplicaciones de la teoría de gráficos espectrales es lo que hoy se conoce como teoría de gráficos químicos , donde un gráfico representa una molécula (generalmente un hidrocarburo ).

El valor propio más grande de un gráfico es simple (es decir, no tiene repeticiones) si y solo si el gráfico está conectado .

El teorema de entrelazado (también conocido como teorema de entrelazado de Cauchy): Si [math] G [/ math] tiene valores propios [math] \ lambda_1 \ geq \ lambda_2 \ geq \ cdots \ geq \ lambda_ {n-1} \ geq \ lambda_n [ / math], luego los valores propios de [math] Gv [/ math], el gráfico [math] G [/ math] con el vértice [math] v [/ math] y sus bordes incidentes eliminados, entrelazan los de [math] G [/ math], es decir, [math] \ lambda_1 \ geq \ mu_1 \ geq \ lambda_2 \ geq \ mu_2 \ geq \ cdots \ geq \ lambda_ {n-1} \ geq \ mu_ {n-1} \ geq \ lambda_n [/ math].

1. En particular, esto significa que si la multiplicidad de [math] \ lambda [/ math] es [math] q [/ math] en [math] G [/ math], entonces la multiplicidad de [math] \ lambda [/ math ] en [matemática] Gv [/ matemática] está entre [matemática] q-1 [/ matemática] y [matemática] q + 1 [/ matemática], ambos inclusive. Corolario: si [math] \ lambda [/ math] no es un valor propio simple en [math] G [/ math], entonces [math] \ lambda [/ math] es un valor propio de [math] Gv [/ math] como bien.
2. Otra consecuencia del teorema de entrelazado: si [math] G [/ math] está conectado, entonces [math] \ mu_1 <\ lambda_1 [/ math], es decir, el valor propio más grande de [math] Gv [/ math] es estrictamente más bajo que el de [matemáticas] G [/ matemáticas].

Si [math] G [/ math] es regular , es decir, sus vértices tienen el mismo grado, entonces su mayor valor propio es igual a este grado.

Un gráfico está completo si y solo si tiene exactamente dos valores propios distintos. Estos valores propios son [matemática] (n-1) [/ matemática] y [matemática] -1 [/ matemática].

Un gráfico es muy regular , es decir, regular de grado [matemático] r [/ matemático] donde cada dos vértices adyacentes tienen [matemático] a [/ matemático] vecinos comunes y cada dos vértices no adyacentes tienen [matemático] b [/ matemática] vecinos comunes, para constantes [matemática] a [/ matemática] y [matemática] b [/ matemática], si y solo si tiene exactamente tres valores propios distintos. Estos valores propios dependen solo de [matemática] r [/ matemática], [matemática] a [/ matemática] y [matemática] b [/ matemática].