Motivación para la teoría de gráfico espectral.

Question

¿Por qué nos preocupamos por los autovalores de gráficos?

Por supuesto, cualquier novela pregunta en matemáticas es muy interesante, pero hay toda una disciplina de las matemáticas dedicada al estudio de estos autovalores, por lo que debe ser importante.

Siempre he asumido que espectrales de la teoría de grafos se extiende la teoría de grafos mediante la provisión de herramientas para probar cosas que no podía de otra manera, algo así como cómo la teoría de la representación se extiende la teoría de grupos. Pero la mayoría de los resultados que veo en el gráfico espectral teoría parece preocupación autovalores no no como medio para un fin, sino como objetos de estudio en su propio derecho.

Yo también considera valor práctico como la motivación, por ejemplo, el uso de un determinado conjunto de valores propios para poner límites a las propiedades esenciales de gráficos, tales como el máximo grado de los vértices. Pero no puedo imaginar una situación en la que me gustaría tener acceso a un gráfico de los valores propios antes me gustaría saber mucho más información elemental como el máximo grado de los vértices.

(EDIT: por ejemplo, dtldarek señala que $\lambda_2$ está relacionada con el diámetro, pero entonces ¿por qué tenemos $\lambda_2$ cuando ya tenemos diámetro? Es de alguna manera conceptualmente beneficioso?)

Así que, ¿cuál es el significado de la gráfica de los espectros de manera intuitiva? Y ¿para qué se usan? ¿Por qué es encontrar los valores propios de un grafo de adyacencia/Laplaciano matrices más que una novela problema?

Answer 1

Esta pregunta ya tiene un número de niza respuestas; quiero destacar la amplitud de de este tema.

Los gráficos pueden ser representados por matrices - matrices de adyacencia y varios sabores de El laplaciano de las matrices. Casi inmediatamente se plantea la cuestión de cuáles son las conexiones entre los espectros de estas matrices y las propiedades de la gráficos. Digamos que el estudio de estas conexiones "la teoría de la gráfica de los espectros". (Pero no estoy del todo contento con esta definición, consulte a continuación). Es tentador ver el mapa en los gráficos a valores propios de una especie de teoría de Fourier, pero hay dificultades con esta analogía. En primer lugar, los gráficos en general no está determinado por el de sus autovalores. Segundo, que muchos de los de las matrices de adyacencia deberíamos utilizar?

Los primeros trabajos en el gráfico espectros se llevó a cabo en el contexto de la Hueckel orbitales moleculares teoría de la Química Cuántica. Esto condujo, entre otras cosas, a trabajar en la coincidencia de polinomio; esto nos da autovalores sin matrices de adyacencia (que es por eso que me siento en la definición del tema es insatisfactorio). Una más reciente la manifestación de esta corriente de ideas es el trabajo en los espectros de los fullerenos.

La segunda fuente de el tema surge en Seidel del trabajo en dos gráficos, lo que comenzó con preguntas acerca de regular simplices en real proyectiva del espacio y llevar a la extraordinariamente interesantes preguntas acerca de los conjuntos de líneas equiángulo en el espacio real. El complejo análogos de estas preguntas ahora son de interés para cuántica los físicos - ver SIC-POVMs. (No está claro qué papel teoría de grafos puede jugar aquí.) En paralelo con Seidel del trabajo fue el papel fundamental de Hoffman y Singleton en Moore gráficos de diámetro, dos. En ambos casos, la clave de la observación fue que ciertos extremal clases de gráficos podría ser caracterizado de manera muy natural por las condiciones en sus espectros. Este trabajo ganó impulso debido a una serie de esporádicos simple grupos se construyó por primera vez como automorphism grupos de gráficos. Para el gráfico los teóricos de esta florecida en la teoría de la distancia-regular gráficos, comenzando con el trabajo de Biggs y sus estudiantes, y todavía muy activo.

Una de las características del papel de Hoffman y Singleton es que su conclusión no hace referencia a los espectros. Por lo que ofrece un importante teórico de gráfico de resultados para que el "libro"a prueba de utiliza los autovalores. Muchos de los resultados a distancia-regular los gráficos de preservar esta característica.

Hoffman también es famosa por su autovalor límites en la cromática de los números, y relacionados con la límites en el tamaño máximo de conjuntos independientes y las camarillas. Esto está estrechamente relacionado con a Lovász el trabajo de Shannon capacidad. Tanto el Erdős-Ko-Rado y teorema de muchos de sus análogos se pueden obtener utilizando las extensiones de estas técnicas.

Los físicos han propuesto algoritmos para la gráfica de isomorfismo basado en los espectros de las matrices asociadas a los discretos y continuos paseos. Las conexiones entre continua cuántica paseos y gráfica de los espectros son muy fuertes.

Answer 2

Yo no puedo hablar mucho a lo tradicional Espectral de la Teoría de grafos se acerca, pero mi investigación personal ha incluido el estudio de lo que yo llamo "Espectral de Realizaciones" de los gráficos. Un espectral de realización es un especial geométricas realización (vértices no son-necesariamente-puntos distintos, los bordes no son-necesariamente-no-degenerada de los segmentos de línea, en algunos $\mathbb{R}^n$) derivadas de los vectores propios de una gráfica de la matriz de adyacencia.

En particular, si las filas de una matriz constituyen una base para algunos de los subespacio propio de la matriz de adyacencia de un grafo de $G$, entonces las columnas de la matriz son las coordenadas de los vectores de (una proyección) de una espectral de realización.

Un espectral de la realización de un gráfico tiene dos bonitas propiedades:

• Es armoniosa: Cada gráfico automorphism induce a una rígida isometría de la realización; se puede ver el gráfico de la automorphic estructura!
• Es eigenic: el Movimiento de cada vértice al vector suma de sus vecinos inmediatos es equivalente a la escala de la figura; el factor de escala es el correspondiente autovalor.

Así, las propiedades son buenas en teoría. Por lo general, un espectral de realización es una mezcla de colapsó segmentos, o que está incorporado es espacio de alta dimensión; tales circunstancias hacen un ejercicio difícil "ver". Sin embargo, una espectral de realización puede ser un útil primer paso en la visualización de un gráfico. Por otra parte, un gráfico con un alto grado de simetría puede admitir algunas visualmente interesante de baja dimensión espectral de realizaciones; por ejemplo, el esqueleto de la octaedro truncado tiene este modestamente-colección elaborada:

Para una galería de cientos de estas cosas, ver el PDF enlazado en mi Bloog post, "Espectral de la Realización de los Gráficos".

Ya que muchos de los objetos matemáticos se descomponen en eigen-objetos, probablemente no es ninguna sorpresa que cualquier geométricas realización de un gráfico es la suma de los espectral de las realizaciones de dicho gráfico. (Simplemente la descomposición de la realización de coordenadas de la matriz en eigen-matrices obtiene la mayor parte de el camino a ese resultado, a pesar de los eigen-matrices de sí mismos generalmente representan "afín" imágenes " de correctamente espectral de realizaciones. El hecho de que afín imágenes descomponer en una suma de similar imágenes se lleva a una extensión de un teorema de Barlotti.) Es probable que haya algo interesante que decir acerca de cómo cada componente espectral espectral influye en las propiedades de la combinación de la figura.

De todos modos ... es por eso Que me importa acerca de los valores propios de los gráficos.

Answer 3

Espectral de la teoría de grafos es un discreto análogo de la geometría espectral, con el Laplaciano en un gráfico de ser un discreto analógica de Laplace-Beltrami operador en un colector de Riemann. El Laplaciano $\Delta$ puede ser utilizado para escribir tres ecuaciones diferenciales, tanto en un gráfico y un colector de Riemann:

• La ecuación del calor $\frac{\partial u}{\partial t} = \Delta u$, que describe cómo el calor se propaga en el gráfico / colector,
• La ecuación de onda de $\frac{\partial^2 u}{\partial t^2} = \Delta u$, que describe cómo las ondas se propagan en el gráfico / colector,
• La ecuación de Schrödinger $i \frac{\partial u}{\partial t} = \Delta u$, que describe cómo las partículas cuánticas se propagan en el gráfico / colector.

El comportamiento de las soluciones a estas ecuaciones es controlado por los autovalores de la Laplaciano. Para la ecuación del calor estos autovalores de control de la velocidad a la que una determinada distribución del calor de desintegración de una distribución estacionaria, y para que la onda de Schrödinger y las ecuaciones de estos autovalores de control de la velocidad a la que la onda estacionaria soluciones de oscilación (esto da una cierta intuición de por qué los autovalores debe estar relacionado con la conectividad de la gráfica). Así que estos autovalores describir algunas importantes propiedades físicas de la gráfica de / colector.

Answer 4

Algunos al azar de los hechos:

• El mayor autovalor $\lambda_1$ está estrechamente relacionado con el grado medio.
• El segundo mayor autovalor $\lambda_2$ está estrechamente relacionado con la conectividad, que es de gráficas con los pequeños $\lambda_2$ tiene de pequeño diámetro.
• Un gráfico de $G$ es bipartito si y sólo si para cada autovalor $\lambda$, $-\lambda$ es también un autovalor.
• Para la conexión de $G$, la cromática cantidad de $G$, $\chi(G) \leq \lambda_1+1$, con igualdad de $G$ ser completa o de un extraño ciclo.
• Algunos utilizan el espectro de la agrupación.

Espero te sirva de ayuda ;-)

Answer 5

Partiendo de un hecho al azar mencionado por dtldarek: las Personas que utilizan con frecuencia espectral de la teoría de grafos en la agrupación.

La situación general es la que tiene una colección de puntos de datos $x_1, \dots x_n$, que pertenecen a algún desconocido clusters $A_1, \dots, A_k$. Desea identificar qué puntos se encuentran en el clúster. De tener algún tipo de conexión gráfica, y la esperanza es que las conexiones tienden a ocurrir dentro de los grupos-por ejemplo, la densidad de los bordes de $A_1$ es mucho mayor que la densidad de bordes de conexión de $A_1$ y $A_2$. Una manera de (intentar) encontrar un clúster, puede ser pensado como la búsqueda de un subconjunto de $Un$ que $$\frac{\textrm{El número de aristas entre los } \textrm{ y el resto del gráfico}}{\textrm{El número total de aristas que involucran}} $$ es extraordinariamente pequeña.

De manera más general, podemos imaginar un grafo ponderado, donde entre cada par de vértices que poner un peso correspondiente a la "cercanía" de los vértices son en algún sentido. El objetivo es, entonces, encontrar un $A$ que el peso total de los bordes entre $A$ y el resto de la gráfica es mucho menor que el peso total de las aristas que involucran $A$.

El problema es que si $G$ $$ n vértices, hay $2^n$ decisiones$$, así que no podemos simplemente buscar todos los si $n$ es grande. Pero lo que a menudo resulta ser una buena aproximación es elegir $$ basada en los vectores propios para el Laplaciano de la matriz de su (ponderado) diagrama de conexión (en particular, los vectores propios correspondientes a los más pequeño distinto de cero autovalores de $L$).

La idea es que si usted toma un vector de $x$ y un gráfico de tener pesos $w_{ij}$ en el eges, entonces $$x^T L x = \sum_{\textrm{bordes } (i,j) } w_{ij} (x_i-x_j)^2$$ En el caso especial donde $x_i=1$ por $i$ en $Un$ y $0$ para $i$ en $Un$, esta se reduzca a $x^T L x$ es el peso total de los bordes de la conexión de $A$ con el resto de la gráfica. Los vectores propios de $L$, con pequeños valores propios corresponden a las opciones de $x$ que $x^T L x$ pequeños.

Para más información sobre esto, consulte este tutorial por Ulrike von Luxburg.