Teoría de grafos espectrales

Aspectos del á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 gráfico simple 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 del vértice, su espectro es un gráfico invariante , aunque no completo.

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

Gráficos cospectrales

Dos gráficos se denominan cospectrales o isospectrales si las matrices de adyacencia de los gráficos son isospectrales , es decir, si las matrices de adyacencia tienen multconjuntos iguales de valores propios.

Dos enneaedros cospectrales , los gráficos poliédricos cospectrales más pequeños posibles

Los gráficos cospectrales no necesitan ser isomórficos , pero los gráficos isomorfos son siempre cospectrales.

Gráficos determinados por su espectro

Se dice que un gráfico está determinado por su espectro si cualquier otro gráfico con el mismo espectro es isomórfico 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 en forma de estrella .

Compañeros espectrales

Se dice que un par de gráficos son compañeros cospectrales si tienen el mismo espectro, pero no son isomórficos.

El par más pequeño de compañeros cospectrales es { K _1,4 , C ₄ ∪ K ₁ }, 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 vértice único, según lo informado por Collatz y Sinogowitz ^{[ 1] [2]} en 1957.

El par más pequeño de parejas cospectrales poliédricas son enneaedros con ocho vértices cada uno. ^[3]

Encontrar gráficos cospectrales

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

Un par de gráficos regulares son cospectrales si y solo si sus complementos son cospectrales. ^[5]

Un par de gráficos de distancia regular son cospectrales si y solo si tienen la misma matriz de intersección.

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

Otra fuente importante de gráficos cospectrales 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 cospectrales, pero a menudo no son isomórficos. ^[7]

Desigualdad de Cheeger

La famosa desigualdad de Cheeger de la geometría riemanniana tiene un análogo discreto que involucra 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 escaso de una gráfica a través del segundo valor propio de su laplaciano.

Constante Cheeger

Artículo principal: constante de Cheeger (teoría de grafos)

La constante de Cheeger (también número de Cheeger o número isoperimétrico ) de un gráfico es una medida numérica de si un gráfico 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, construcción de redes de computadoras bien conectadas , barajado de cartas y topología de baja dimensión (en particular, el estudio de tres variedades hiperbólicas ).

Más formalmente, la constante de Cheeger h ( G ) de un gráfico 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 más de todos los conjuntos no vacíos S de en la mayoría de n / 2 vértices y ∂ ( S ) es el límite del borde de S , es decir, el conjunto de bordes con exactamente un punto final en S . ^[8]

Desigualdad de Cheeger

Cuando el gráfico G es d -regular, hay una relación entre h ( G ) y la brecha espectral d - λ ₂ de G . Una desigualdad debida a Dodziuk ^[9] e independientemente Alon y Milman ^[10] afirman 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 riemanniana .

Desigualdad de Hoffman-Delsarte

Hay un valor propio ligado a conjuntos independientes en gráficos regulares , originalmente debido a Alan J. Hoffman y Philippe Delsarte. ^[12]

Suponga que es un grafo regular en vértices con el mínimo valor propio . Luego:${\displaystyle G}$${\displaystyle k}$${\displaystyle n}$${\displaystyle \lambda _{\mathrm {min} }}$

$${\displaystyle \alpha (G)\leq {\frac {n}{1-{\frac {k}{\lambda _{\mathrm {min} }}}}}}$$

donde denota su número de independencia .${\displaystyle \alpha (G)}$

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

Esquema histórico

La teoría de los gráficos espectrales surgió en las décadas de 1950 y 1960. Además de la investigación de la teoría de los gráficos sobre la relación entre las propiedades estructurales y espectrales de los gráficos, 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 más tarde. ^[14] La monografía de 1980 Spectra of Graphs ^[15] de Cvetković, Doob y Sachs resumió casi todas las investigaciones realizadas hasta la fecha en el área. En 1988 fue actualizado por la encuesta Recent Results in the Theory of Graph Spectra . ^[16] La tercera edición de Spectra of Graphs (1995) contiene un resumen de las contribuciones más recientes al tema.^{[14] El} análisis geométrico discreto creado y desarrollado por Toshikazu Sunada en la década de 2000 se ocupa de la teoría de grafos espectrales en términos de laplacianos discretos asociados con grafos ponderados, ^[17] 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 de vértices variables que se encuentran a menudo en muchas aplicaciones de la vida real. ^{[18] [19] [20] [21]}

Ver también

• Gráfico muy regular
• Conectividad algebraica
• Teoría de grafos algebraicos
• Agrupación espectral
• Análisis de forma espectral
• Índice de Estrada
• Lovász theta
• 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 espectrales" . MathWorld .
3. Hosoya, Haruo ; Nagashima, Umpei; Hyugaji, Sachiko (1994), "Gráficos gemelos topológicos. El par más pequeño de gráficos poliédricos isospectrales 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 espectrales?" (PDF) .
6. Sunada, Toshikazu (1985), "Coberturas riemannianas y variedades isospectrales", Ann. de Matemáticas. , 121 (1): 169–186, doi : 10.2307 / 1971195 , JSTOR 1971195 .
7. Ver ( Brouwer & Haemers 2011 ) en los enlaces externos .
8. Definición 2.1 en Hoory, Linial & Widgerson (2006)error de harvtxt: sin destino: CITEREFHooryLinialWidgerson2006 ( ayuda )
9. J.Dodziuk, Ecuaciones en diferencias, desigualdad isoperimétrica y fugacidad de ciertos paseos al azar, Trans. Amer. Matemáticas. Soc. 284 (1984), núm. 2, 787-794.
10. Alon y Spencer 2011 . sfn error: no target: CITEREFAlonSpencer2011 (help)
11. Teorema 2.4 en Hoory, Linial y Widgerson (2006) harvtxt error: no target: CITEREFHooryLinialWidgerson2006 (help)
12. Godsil, Chris (mayo de 2009). "Teoremas de Erdős-Ko-Rado" (PDF) .
13. 1949-, Godsil, CD (Christopher David) (2016). Teoremas de Erdős-Ko-Rado: enfoques algebraicos . Meagher, Karen (profesora universitaria). Cambridge, Reino Unido. ISBN 9781107128446. OCLC  935456305 .
14. Espacios propios de gráficos , por Dragoš Cvetković , Peter Rowlinson, Slobodan Simić (1997) ISBN 0-521-57352-1 
15. Dragoš M. Cvetković, Michael Doob, Horst Sachs , Espectros de gráficos (1980)
16. Cvetković, Dragoš M .; Doob, Michael; Gutman, Ivan; Torgasev, A. (1988). Resultados recientes en la teoría de espectros gráficos . Anales de matemáticas discretas. ISBN 0-444-70361-6.
17. Sunada, Toshikazu (2008), "Análisis geométrico discreto", Actas de simposios en matemáticas puras , 77 : 51-86, doi : 10.1090 / pspum / 077/2459864 , ISBN 9780821844717.
18. Shuman, David I; Ricaud, Benjamín; Vandergheynst, Pierre (marzo de 2016). "Análisis de frecuencia de vértice en gráficos". 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 . 
19. Stankovic, Ljubisa; Dakovic, Milos; Sejdic, Ervin (julio de 2017). "Análisis de frecuencia de vértice: una forma de localizar los componentes espectrales del gráfico [notas de la conferencia]". Revista de procesamiento de señales IEEE . 34 (4): 176–182. Código bibliográfico : 2017ISPM ... 34..176S . doi : 10.1109 / msp.2017.2696572 . ISSN 1053-5888 . 
20. Sakiyama, Akie; Watanabe, Kana; Tanaka, Yuichi (septiembre de 2016). "Wavelets de gráfico espectral y bancos de filtros con error de aproximación bajo". Transacciones IEEE sobre procesamiento de señales e información a través de redes . 2 (3): 230–245. doi : 10.1109 / tsipn.2016.2581303 . ISSN 2373-776X . 
21. 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" . Transacciones IEEE sobre procesamiento de señales . 64 (22): 6017–6029. Código bibliográfico : 2016ITSP ... 64.6017B . doi : 10.1109 / tsp.2016.2591513 . ISSN 1053-587X . 

• Schwenk, AJ (1973). "Casi todos los árboles son cospectrales". En Harary, Frank (ed.). Nuevas direcciones en la teoría de los gráficos . Nueva York: Academic Press . ISBN 012324255X. OCLC  890297242 .

Lectura adicional

• Chung, Fan (1997). Sociedad Americana de Matemáticas (ed.). Teoría del gráfico espectral . Providencia, RI ISBN 0821803158. MR  1421568 [los primeros 4 capítulos están disponibles en el sitio web]

Enlaces externos

• Brouwer, Andries ; Haemers, Willem H. (2011). "Espectros de gráficos" (PDF) .
• Spielman, Daniel (2011). "Teoría del gráfico espectral" (PDF) . [capítulo de Computación científica combinatoria]
• Spielman, Daniel (2007). "Teoría del gráfico espectral y sus aplicaciones" . [presentado en la Conferencia FOCS 2007]
• Spielman, Daniel (2004). "Teoría del gráfico espectral y sus aplicaciones" . [página del curso y notas de la clase]