Teoría espectral de los grafos: interpretabilidad de los valores propios y los vectores

Question

Pensé "¡Guau!" cuando aprendí que el vector propio de la matriz de adyacencia de un gráfico de ciclo $C_n$ correspondiente al segundo mayor valor propio da las coordenadas de los vértices cuando se distribuyen por igual en el ciclo unitario: el $n$ -Las raíces de la unidad (del análisis complejo) aparecen en un contexto completamente discreto. Es más: Las coordenadas del vector propio pueden ser "interpretadas" directamente cuando se asignan correctamente a los vértices.

Hay otra interpretación directa de un vector propio de adyacencia: el vector propio correspondiente al mayor valor propio da la importancia relativa de los vértices siendo proporcional a la suma de las importancias relativas de sus vecinos.

Pregunta: ¿Se pueden "interpretar" más vectores propios de adyacencia, o todos ellos, de forma razonable? "interpretados"?

¿O, en general, depende del tipo de gráfico, de si se pueden interpretar los vectores propios y de cómo se pueden interpretar, y el primer ejemplo anterior es sólo una curiosidad?

¿Qué pasa con la interpretación de los eigen- valores ? ¿Al menos algunos de ellos "significan" algo concebible?

Answer 1

Si el gráfico tiene un eigespacio de dimensión superior a uno, entonces va a va a ser difícil relacionar las propiedades de los vectores propios con las propiedades del gráfico. Una forma de evitar esto es trabajar con las proyecciones ortogonales sobre el eigespacio. Si $A$ es la matriz de adyacencia, entonces $$ A^r =\sum_\theta \theta^r E_\theta $$ donde $\theta$ recorre los distintos valores propios y $E_\theta$ es la proyección sobre el $\theta$ -eigenspace. De esto vemos que los valores propios junto con las entradas de $E_\theta$ dan información precisa sobre los paseos en el gráfico, e información general sobre las propiedades de expansión.

Hay muchas formas naturales de representar un gráfico mediante una matriz. Por ejemplo se podría argumentar que deberíamos utilizar $-A$ en lugar de $A$ . Esto sugiere que asignar un significado a los valores propios puede ser difícil, pero hace menos sorprendente que existan límites útiles sobre el tamaño de las camarillas y el número cromático que implican de valores propios (véase "Límites de Hoffman").

Para muchos gráficos planos (por ejemplo, fullerenos ), la imagen de la proyección de una base estándar sobre la suma de los eigespacios segundo a cuarto es un politopo cuyo esqueleto 1 suele ser el gráfico original. Esto se relaciona con la expresión de Tutte " Cómo dibujar un gráfico " y a trabajar en el número de Colin de Verdiere, pero es justo decir que no podemos explicar realmente lo que está pasando aquí.

Answer 2

Sí: todos los vectores de adyacencia pueden interpretarse de forma razonable.

Voy a repetir una respuesta que di a otro otra pregunta ...

Una matriz cuya filas forman una base ortogonal de un eigespacio de la matriz de adyacencia de un grafo tiene columnas que sirven como vectores de coordenadas de un armonioso realización geométrica del gráfico.

("armonioso" == los automorfismos del grafo inducen isometrías rígidas la realización)

Cuando el gráfico tiene un alto grado de simetría, estas realizaciones -que yo llamo "espectrales"- tienen un gran atractivo visual; sin embargo, en general, estas realizaciones son revoltijos de puntos en un espacio unidimensional. En la mayoría de los casos, los vértices (y aristas) múltiples se reducen a puntos individuales, de modo que las realizaciones no son fiel .

[*] Más precisamente, las realizaciones tal como se describen aquí son proyecciones ortogonales de realizaciones que yo llamo "espectrales". (Véase mi nota aún redactada, "Realizaciones espectrales de grafos" que está dedicado a una galería de muchas realizaciones espectrales de los poliedros uniformes. Véase también mi Mathematica Demostración "Realizaciones espectrales de esqueletos poliédricos" .)

Answer 3

Otro caso divertido es el del gráfico icosaédrico truncado (denominado químicamente Buckminsterfullereno cuando se realiza como un clúster de carbono de 60 átomos). En este caso, el segundo valor propio es triplemente degenerado, y si x, y, z denotan 3 vectores propios reales equi-normales para este valor propio, entonces los 60 triples de componentes correspondientes localizan los vértices como incrustados en el espacio euclidiano para manifestar la simetría icosaédrica. Véase: D. E. Manopolous & P. W. Fowler, J. Chem. Phys. 96 (1992) 7603-7615 . De hecho, estos autores tratan de forma similar otros "fullerenos" (que son poliedros con vértices de grado 3 y caras que son pentágonos o hexágonos). En general, los valores propios requeridos no son degenerados, sino que son aquellos que tienen vectores propios con componentes que dividen el gráfico en exactamente 2 regiones conectadas de diferentes signos para los componentes -- también se utiliza algún tipo de escala de los componentes por fucciones apropiadas de los diferentes valores propios. Se han realizado algunos trabajos adicionales sobre estas ideas para otros grafos adecuados; para el caso no regular, es posible que se prefiera la matriz laplaiana a la matriz de adyacencia.
Lo que ocurre puede "entenderse" intuitivamente, mejor en términos del laplaciano, que es un análogo discreto del laplaciano clásico del análisis. Para este Laplaciano clásico, los vectores propios corresponden a ondas estacionarias con la energía correspondiente al valor propio. Las ondas largas que tienen un único nodo interno dividen la región (es decir, el gráfico en nuestra analogía) con las amplitudes que dan las distancias desde el nodo.
También existe el esquema "clásico" de W. T. Tutte para "dibujar" el diagrama de Schlegel de un grafo poliédrico: Proc. London Math. Soc. 13 (1963) 743-767. Para un estudio más reciente sobre los "Puentes entre la Geometría y la Teoría de Grafos", véase T. Pisanski & M. Randic, páginas 174-194 en Geopmetry at Work, ed. C. A. Gorini (MAA, Wash. DC, 2000).

Answer 4

(Pretendía ser un comentario a la respuesta de Chris Godsil, pero es demasiado largo).

Una forma de precisar la última afirmación de la respuesta de Chris Godsil es la siguiente: Consideremos un gráfico plano que es $3-$ borde conectado. Por un famoso teorema, es entonces el 1-esqueleto de un $3-$ politopo dimensional. Elegir pesos positivos en las aristas de tal manera que la matriz de adyacencia resultante más una matriz diagonal adecuada (un operador de Schroedinger) tenga un espacio de eigenes de dimensión $3$ para el segundo valor propio más pequeño. Además, necesitamos una condición de estabilidad ligeramente técnica: el conjunto de todos los operadores de Schroedinger en el gráfico tiene que ser transversal en la matriz elegida al conjunto de todas las matrices simétricas con el segundo valor propio más pequeño de multiplicidad $3$
(esta es una condición de estabilidad que permite pequeñas perturbaciones). Las coordenadas de cualquier base del segundo valor propio más pequeño son entonces las coordenadas de los vértices de un $3-$ politopo dimensional que realiza el gráfico. (Dicha base debe ser cercana a la $2-$ n hasta el $4-$ los vectores propios más pequeños, de ahí la observación de Chris Godsil.

También existen generalizaciones parciales de esta construcción relacionadas con grafos con número de Colin de Verdiere mayor que $3$ .

Answer 5

En cuanto a las interpretaciones de los valores propios, recuerdo que el espectro de un gráfico puede indicar si es bipartito. Creo que un gráfico conectado es bipartito si y sólo si $-\lambda$ es uno de sus valores propios (aquí $\lambda$ es el mayor valor propio). Por favor, corrígeme si he confundido el teorema.