Teoría de grafos espectrales

En matemáticas , la teoría de grafos espectrales es el estudio de las propiedades de un grafo en relación con el polinomio característico , los valores propios y los vectores propios de las matrices asociadas con el grafo, como su matriz de adyacencia o matriz laplaciana .

La matriz de adyacencia de un grafo simple no dirigido es una matriz simétrica real y, por lo tanto, es diagonalizable ortogonalmente ; sus valores propios son números enteros algebraicos reales .

Si bien la matriz de adyacencia depende del etiquetado de los vértices, su espectro es un gráfico invariante , aunque no completo.

La teoría de grafos espectrales también se ocupa de los parámetros del grafo que se definen a través de multiplicidades de valores propios de matrices asociadas al grafo, como el número de Colin de Verdière .

Dos gráficos se denominan coespectrales o isoespectrales si las matrices de adyacencia de los gráficos son isoespectrales , es decir, si las matrices de adyacencia tienen multiconjuntos iguales de valores propios.

Los gráficos coespectrales no necesitan ser isomorfos , pero los gráficos isomorfos siempre son coespectrales.

Se dice que un grafo está determinado por su espectro si cualquier otro grafo con el mismo espectro que es isomorfo a .${\estilo de visualización G}$${\estilo de visualización G}$${\estilo de visualización G}$

Algunos primeros ejemplos de familias de gráficos que están determinadas por su espectro incluyen:

• Los gráficos completos .
• Los árboles finitos con forma de estrella .

Se dice que un par de gráficos son compañeros coespectrales si tienen el mismo espectro, pero no son isomorfos.

El par más pequeño de compañeros coespectrales es { K _1,4 , C ₄ ∪ K _{1 }, que comprende la} estrella de 5 vértices y la unión gráfica del ciclo de 4 vértices y el gráfico de un solo vértice, como informaron Collatz y Sinogowitz ^{[1] [2]} en 1957.

El par más pequeño de compañeros coespectrales poliédricos son eneaedros con ocho vértices cada uno. ^[3]

Casi todos los árboles son coespectrales, es decir, a medida que aumenta el número de vértices, la fracción de árboles para los que existe un árbol coespectral tiende a 1. ^[4]

Un par de gráficos regulares son coespectrales si y sólo si sus complementos son coespectrales. ^[5]

Un par de gráficos regulares en cuanto a distancia son coespectrales si y solo si tienen la misma matriz de intersecciones.

Los gráficos coespectrales también se pueden construir mediante el método Sunada . ^[6]

Otra fuente importante de gráficos coespectrales son los gráficos de colinealidad de puntos y los gráficos de intersección de líneas de geometrías de puntos y líneas . Estos gráficos son siempre coespectrales, pero a menudo no son isomorfos. ^[7]

La famosa desigualdad de Cheeger de la geometría de Riemann tiene un análogo discreto que involucra a la matriz laplaciana; este es quizás el teorema más importante en la teoría de grafos espectrales y uno de los hechos más útiles en aplicaciones algorítmicas. Aproxima el corte más disperso de un grafo a través del segundo valor propio de su laplaciano.

La constante de Cheeger (también llamada número de Cheeger o número isoperimétrico ) de un grafo es una medida numérica de si un grafo tiene o no un "cuello de botella". La constante de Cheeger como medida de "cuello de botella" es de gran interés en muchas áreas: por ejemplo, la construcción de redes de computadoras bien conectadas , el barajado de cartas y la topología de baja dimensión (en particular, el estudio de variedades hiperbólicas de 3 dimensiones ).

Más formalmente, la constante de Cheeger h ( G ) de un grafo G en n vértices se define como

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},}$

donde el mínimo es sobre todos los conjuntos no vacíos S de como máximo n /2 vértices y ∂( S ) es el límite de la arista de S , es decir, el conjunto de aristas con exactamente un punto final en S . ^[8]

Cuando el grafo G es d -regular, existe una relación entre h ( G ) y el gap espectral d − λ ₂ de G . Una desigualdad debida a Dodziuk ^[9] e independientemente a Alon y Milman ^[10] establece que ^[11]

${\displaystyle {\frac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

Esta desigualdad está estrechamente relacionada con el límite de Cheeger para las cadenas de Markov y puede verse como una versión discreta de la desigualdad de Cheeger en la geometría de Riemann .

^{Para gráficos generales conectados que no son necesariamente regulares, Chung [12]} da una desigualdad alternativa ^{: 35}

${\displaystyle {\frac {1}{2}}{\lambda }\leq {\mathbf {h} }(G)\leq {\sqrt {2\lambda }},}$

donde es el valor propio no trivial más pequeño del laplaciano normalizado, y es la constante de Cheeger (normalizada) ${\estilo de visualización \lambda}$${\displaystyle {\mathbf {h}}(G)}$

${\displaystyle {\mathbf {h} }(G)=\min _{\conjunto vacío \no =S\subconjunto V(G)}{\frac {|\partial (S)|}{\min({\mathrm {vol} }(S),{\mathrm {vol} }({\bar {S}}))}}}$

donde es la suma de los grados de los vértices en .${\displaystyle {\mathrm {vol} }(Y)}$${\estilo de visualización Y}$

Existe un límite de valor propio para conjuntos independientes en grafos regulares , originalmente debido a Alan J. Hoffman y Philippe Delsarte. ^[13]

Supongamos que es un grafo regular en vértices con el menor valor propio . Entonces: donde denota su número de independencia .${\estilo de visualización G}$${\estilo de visualización k}$${\estilo de visualización n}$${\displaystyle \lambda _ {\mathrm {min} }}$$${\displaystyle \alpha (G)\leq {\frac {n}{1-{\frac {k}{\lambda _{\mathrm {min} }}}}}}$$${\displaystyle \alpha (G)}$

Este límite se ha aplicado para establecer, por ejemplo, pruebas algebraicas del teorema de Erdős–Ko–Rado y su análogo para familias de subespacios que se intersecan sobre campos finitos . ^[14]

Para los grafos generales que no son necesariamente regulares, se puede derivar un límite superior similar para el número de independencia utilizando el valor propio máximo del laplaciano normalizado ^[12] de : donde y denotan el grado máximo y mínimo en , respectivamente. Esto es una consecuencia de una desigualdad más general (pp. 109 en ^[12] ): donde es un conjunto independiente de vértices y denota la suma de los grados de los vértices en .${\displaystyle \lambda '_{max}}$${\estilo de visualización G}$$${\displaystyle \alpha (G)\leq n(1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\frac {\mathrm {maxdeg} }{\mathrm {mindeg } }}}$$${\displaystyle {\mathrm {maxdeg} }}$${\displaystyle {\mathrm {mindeg} }}$${\estilo de visualización G}$$${\displaystyle {\mathrm {vol} }(X)\leq (1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\mathrm {vol} }(V(G ))}$$${\estilo de visualización X}$${\displaystyle {\mathrm {vol} }(Y)}$${\estilo de visualización Y}$

La teoría de grafos espectrales surgió en los años 1950 y 1960. Además de la investigación teórica de grafos sobre la relación entre las propiedades estructurales y espectrales de los grafos, otra fuente importante fue la investigación en química cuántica , pero las conexiones entre estas dos líneas de trabajo no se descubrieron hasta mucho después. ^[15] La monografía Spectra of Graphs ^[16] de 1980 de Cvetković, Doob y Sachs resumió casi toda la investigación hasta la fecha en el área. En 1988 fue actualizada por la encuesta Recent Results in the Theory of Graph Spectra . ^[17] La ​​tercera edición de Spectra of Graphs (1995) contiene un resumen de las contribuciones recientes adicionales al tema. ^[15] El análisis geométrico discreto creado y desarrollado por Toshikazu Sunada en la década de 2000 trata la teoría de grafos espectrales en términos de laplacianos discretos asociados con grafos ponderados, ^[18] y encuentra aplicación en varios campos, incluido el análisis de formas . En los últimos años, la teoría de grafos espectrales se ha expandido a grafos que varían en los vértices y que suelen encontrarse en muchas aplicaciones de la vida real. ^{[19] [20] [21] [22]}

• Gráfico fuertemente regular
• Conectividad algebraica
• Teoría de grafos algebraicos
• Agrupamiento espectral
• Análisis de la forma espectral
• Índice de Estrada
• Theta de Lovász
• Gráfico expansor

• Alon; Spencer (2011), El método probabilístico , Wiley.
• Brouwer, Andries ; Haemers, Willem H. (2011), Espectros de gráficos (PDF) , Springer
• Hoory; Linial; Wigderson (2006), Gráficos expansores y sus aplicaciones (PDF)
• Chung, Fan (1997). Sociedad Americana de Matemáticas (ed.). Teoría de grafos espectrales. Providence, RI ISBN 0821803158.MR 1421568[ los  primeros 4 capítulos están disponibles en el sitio web]{{cite book}}: Mantenimiento de CS1: postscript ( enlace )
• Schwenk, AJ (1973). "Casi todos los árboles son coespectrales". En Harary, Frank (ed.). Nuevas direcciones en la teoría de grafos . Nueva York: Academic Press . ISBN 012324255X.OCLC 890297242  .
• Bogdan, Nica (2018). "Una breve introducción a la teoría de grafos espectrales" . Zúrich: EMS Press. ISBN 978-3-03719-188-0.
• Pavel Kurasov (2024), Geometría espectral de gráficos, Springer (Birkhauser), acceso abierto (CC4.0).

• Spielman, Daniel (2011). "Teoría de grafos espectrales" (PDF) .[Capítulo de Computación científica combinatoria]
• Spielman, Daniel (2007). "Teoría de grafos espectrales y sus aplicaciones".[Presentado en la Conferencia FOCS 2007]
• Spielman, Daniel (2004). "Teoría de grafos espectrales y sus aplicaciones".[Página del curso y notas de la conferencia]