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 matrices asociadas con el grafo, como su matriz de adyacencia o matriz laplaciana .

La matriz de adyacencia de un gráfico simple no dirigido es una matriz simétrica real y, por tanto, es ortogonalmente diagonalizable ; 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 de grafos que se definen mediante multiplicidades de valores propios de matrices asociadas al gráfico, como el número de Colin de Verdière .

Gráficos cospectrales

Dos gráficos se llaman coespectrales o isoespectrales si las matrices de adyacencia de los gráficos son isoespectrales , es decir, si las matrices de adyacencia tienen múltiples conjuntos iguales de valores propios.

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

Los gráficos coespectrales no tienen por qué ser isomórficos , pero los gráficos isomórficos siempre son coespectrales.

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 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 en forma de estrellas .

Compañeros cospectrales

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, según lo informado por 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 crece el número de vértices, la fracción de árboles para los que existe un árbol coespectral pasa a 1. ^[4]

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

Un par de gráficos de distancia regular son coespectrales si y sólo si tienen la misma matriz de intersecciones.

También se pueden construir gráficos coespectrales 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 líneas de puntos . Estos gráficos son siempre coespectrales pero a menudo no isomorfos. ^[7]

Desigualdad de Cheeger

La famosa desigualdad de Cheeger de la geometría de Riemann 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. Se aproxima al corte más escaso de un gráfico a través del segundo valor propio de su laplaciano.

constante de alegría

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, 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 3 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 está sobre todos los conjuntos no vacíos S de como máximo n /2 vértices y ∂( S ) es el límite de 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, existe una relación entre h ( G ) y la brecha espectral d − λ ₂ de G . Una desigualdad debida a Dodziuk ^[9] e independientemente a Alon y Milman ^[10] afirma 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 menos no trivial 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

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

Supongamos que es un gráfico regular en vértices con el menor valor propio . Entonces: ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle \lambda _{\mathrm {min} }}$

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

número de independencia ${\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 la intersección de familias de subespacios sobre campos finitos . ^[14]

Para gráficos 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 : ${\displaystyle \lambda '_{max}}$ ${\displaystyle G}$

$${\displaystyle \alpha (G)\leq n(1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\frac {\mathrm {maxdeg} }{\mathrm {mindeg} }}}$$

^[12] ${\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 las décadas de 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 más tarde. ^[15] La monografía de 1980 Spectra of Graphs ^[16] de Cvetković, Doob y Sachs resumió casi toda la investigación hasta la fecha en el área. En 1988 fue actualizado por la encuesta Resultados Recientes en la Teoría de Espectros de Grafos . ^[17] La ​​tercera edición de Spectra of Graphs (1995) contiene un resumen de las contribuciones recientes al tema. ^[15] 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 gráficos ponderados, ^[18] y encuentra aplicación en varios campos, incluido el análisis de formas . En los años más recientes, la teoría de gráficos espectrales se ha expandido a gráficos con variación de vértices que a menudo se encuentran en muchas aplicaciones de la vida real. ^{[19] [20] [21] [22]}

Ver también

• Gráfico fuertemente regular
• Conectividad algebraica
• Teoría de grafos algebraicos
• Agrupación espectral
• Análisis de forma espectral
• índice de Estrada
• theta de lovász
• Gráfico de expansión

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 cospectrales". MundoMatemático .
3. Hosoya, Haruo ; Nagashima, Umpei; Hyugaji, Sachiko (1994), "Gráficos gemelos topológicos. El par más pequeño de gráficos 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). "¿Casi todos los gráficos son coespectrales?" (PDF) .
6. Sunada, Toshikazu (1985), "Revestimientos riemannianos y variedades isoespectrales", Ann. de Matemáticas. , 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 en diferencias, desigualdad isoperimétrica y transitoriedad de ciertos paseos aleatorios, Trans. América. Matemáticas. 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, ventilador (1997). Sociedad Estadounidense de Matemáticas (ed.). Teoría de grafos espectrales. Providencia, Rhode Island ISBN 0821803158. MR  1421568[los primeros 4 capítulos están disponibles en el sitio web]{{cite book}}: Mantenimiento CS1: posdata ( enlace )
13. Godsil, Chris (mayo de 2009). "Teoremas de Erdős-Ko-Rado" (PDF) .
14. Diossil, CD; Más fuerte, Karen (2016). Teoremas de Erdős-Ko-Rado: enfoques algebraicos . Cambridge, Reino Unido. ISBN 9781107128446. OCLC  935456305.{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( 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, Iván; Torgasev, A. (1988). Resultados recientes en la teoría de los 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 de matemática pura , 77 : 51–86, doi :10.1090/pspum/077/2459864, ISBN 9780821844717.
19. Humano, David I; Ricaud, Benjamín; Vandergheynst, Pierre (marzo de 2016). "Análisis de frecuencia de vértices en gráficos". Análisis Armónico Aplicado y Computacional . 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 la conferencia]". Revista de procesamiento de señales IEEE . 34 (4): 176–182. Código Bib : 2017 ISPM...34..176S. doi :10.1109/msp.2017.2696572. ISSN  1053-5888. S2CID  19969572.
21. Sakiyama, Akie; Watanabe, Kana; Tanaka, Yuichi (septiembre de 2016). "Ondas de gráficos espectrales y bancos de filtros con bajo error de aproximación". 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. 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". Transacciones IEEE sobre procesamiento de señales . 64 (22): 6017–6029. Código Bib : 2016ITSP...64.6017B. doi :10.1109/tsp.2016.2591513. ISSN  1053-587X. S2CID  12844791.

• Solo; Spencer (2011), El método probabilístico , Wiley.
• Brouwer, Andries ; Haemers, Willem H. (2011), Espectros de gráficos (PDF) , Springer
• Hoori; Linial; Wigderson (2006), Gráficos de expansión y sus aplicaciones (PDF)
• Chung, ventilador (1997). Sociedad Estadounidense de Matemáticas (ed.). Teoría de grafos espectrales. Providencia, Rhode Island ISBN 0821803158. MR  1421568[los primeros 4 capítulos están disponibles en el sitio web]{{cite book}}: Mantenimiento CS1: posdata ( enlace )
• Schwenk, AJ (1973). "Casi todos los árboles son espectrales". En Harary, Frank (ed.). Nuevas direcciones en la teoría de grafos . Nueva York: Prensa académica . ISBN 012324255X. OCLC  890297242.

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