Teoría de grafos espectrales

Aspectos de álgebra lineal de la teoría de grafos

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 .

Gráficos coespectrales

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.

Dos eneaedros coespectrales , los grafos poliédricos coespectrales más pequeños posibles

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

Gráficas determinadas por su espectro

Se dice que un grafo está determinado por su espectro si cualquier otro grafo con el mismo espectro que es isomorfo a . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle 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 .

Compañeros coespectrales

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]

Encontrar gráficos coespectrales

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]

Desigualdad de Cheeger

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.

Cheeger constante

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]

Desigualdad de Cheeger

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) ${\displaystyle \lambda }$ ${\displaystyle {\mathbf {h} }(G)}$

${\displaystyle {\mathbf {h} }(G)=\min _{\emptyset \not =S\subset 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)}$ ${\displaystyle Y}$

Desigualdad de Hoffman-Delsarte

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 . ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle 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}}$ ${\displaystyle G}$ $${\displaystyle \alpha (G)\leq n(1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\frac {\mathrm {maxdeg} }{\mathrm {mindeg} }}}$$ ${\displaystyle {\mathrm {maxdeg} }}$ ${\displaystyle {\mathrm {mindeg} }}$ ${\displaystyle G}$ $${\displaystyle {\mathrm {vol} }(X)\leq (1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\mathrm {vol} }(V(G))}$$ ${\displaystyle X}$ ${\displaystyle {\mathrm {vol} }(Y)}$ ${\displaystyle Y}$

Esquema histórico

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]}

Véase también

• 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

Referencias

1. Collatz, L. y Sinogowitz, U. "Spektren endlicher Grafen". Abh. Matemáticas. Sem. Univ. Hamburgo 21, 63–77, 1957.
2. Weisstein, Eric W. "Gráficos coespectrales". MathWorld .
3. Hosoya, Haruo ; Nagashima, Umpei; Hyugaji, Sachiko (1994), "Gráficos gemelos topológicos. Par más pequeño de grafos poliédricos isoespectrales con ocho vértices", Journal of Chemical Information and Modeling , 34 (2): 428–431, doi :10.1021/ci00018a033.
4. Schwenk (1973), págs. 275–307.
5. Godsil, Chris (7 de noviembre de 2007). "¿Son casi todos los gráficos coespectrales?" (PDF) .
6. Sunada, Toshikazu (1985), "Recubrimientos riemannianos y variedades isoespectrales", Ann. of Math. , 121 (1): 169–186, doi :10.2307/1971195, JSTOR  1971195.
7. Brouwer y Haemers 2011
8. Definición 2.1 en Hoory, Linial y Wigderson (2006)
9. J. Dodziuk, Ecuaciones diferenciales, desigualdad isoperimétrica y transitoriedad de ciertos recorridos aleatorios, Trans. Amer. Math. Soc. 284 (1984), núm. 2, 787-794.
10. Alon y Spencer 2011.
11. Teorema 2.4 en Hoory, Linial y Wigderson (2006)
12. Chung, Fan (1997). Sociedad Matemática Estadounidense (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 )
13. Godsil, Chris (mayo de 2009). "Teoremas de Erdős-Ko-Rado" (PDF) .
14. Godsil, CD; Meagher, Karen (2016). Teoremas de Erdős-Ko-Rado: enfoques algebraicos . Cambridge, Reino Unido. ISBN 9781107128446.OCLC 935456305  .{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
15. Espacios propios de gráficos , por Dragoš Cvetković, Peter Rowlinson, Slobodan Simić (1997) ISBN 0-521-57352-1 
16. Dragoš M. Cvetković, Michael Doob, Horst Sachs , Espectros de gráficos (1980)
17. Cvetković, Dragoš M.; Doob, Michael; Gutman, Ivan; Torgasev, A. (1988). Resultados recientes en la teoría de espectros de grafos. Anales de matemáticas discretas. ISBN 0-444-70361-6.
18. Sunada, Toshikazu (2008), "Análisis geométrico discreto", Actas de simposios sobre matemáticas puras , 77 : 51–86, doi :10.1090/pspum/077/2459864, ISBN 9780821844717.
19. Shuman, David I; Ricaud, Benjamin; Vandergheynst, Pierre (marzo de 2016). "Análisis de frecuencia de vértice en grafos". Análisis armónico computacional y aplicado . 40 (2): 260–291. arXiv : 1307.5708 . doi :10.1016/j.acha.2015.02.005. ISSN  1063-5203. S2CID  16487065.
20. Stankovic, Ljubisa; Dakovic, Milos; Sejdic, Ervin (julio de 2017). "Análisis de frecuencia de vértice: una forma de localizar componentes espectrales de gráficos [Notas de clase]". Revista IEEE de procesamiento de señales . 34 (4): 176–182. Bibcode :2017ISPM...34..176S. doi :10.1109/msp.2017.2696572. ISSN  1053-5888. S2CID  19969572.
21. Sakiyama, Akie; Watanabe, Kana; Tanaka, Yuichi (septiembre de 2016). "Ondeletas de gráficos espectrales y bancos de filtros con bajo error de aproximación". IEEE Transactions on Signal and Information Processing over Networks . 2 (3): 230–245. doi :10.1109/tsipn.2016.2581303. ISSN  2373-776X. S2CID  2052898.
22. Behjat, Hamid; Richter, Ulrike; Van De Ville, Dimitri; Sornmo, Leif (15 de noviembre de 2016). "Marcos ajustados adaptados a la señal en gráficos". IEEE Transactions on Signal Processing . 64 (22): 6017–6029. Bibcode :2016ITSP...64.6017B. doi :10.1109/tsp.2016.2591513. ISSN  1053-587X. S2CID  12844791.

• 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.

Enlaces externos

• 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]