Los valores propios medios de un grafo no dirigido

Question

Sea $ \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_{2n} $ sea la colección de valores propios de una matriz de adyacencia de un grafo no dirigido $G$ en $2n$ vértices. Busco cualquier trabajo o referencia que considere los valores propios medios $\lambda_n$ y $\lambda_{n+1}$ . En particular, los límites de $R(G) = \max \left( |\lambda_n|, |\lambda_{n+1}| \right)$ son bienvenidos.

Por ejemplo, una búsqueda informática demostró que la mayoría de los grafos conectados con máxima valencia $3$ tienen $R(G) \le 1$ . La única excepción conocida es el gráfico de Heawood.

La motivación de esta pregunta proviene de la química teórica, donde la diferencia $\lambda_n - \lambda_{n+1}$ en la teoría de Hueckel se denomina Separación HOMO-LUMO .

Edita: Obsérvese que en la fórmula original para $R(G)$ faltaban los signos de valor absoluto.

Answer 1

Si el grafo es bipartito (una restricción natural si la motivación procede de la teoría de Hueckel), la simetría del espectro es bastante reveladora. Si 0 es un valor propio del grafo, entonces es un valor propio doble, y por tanto $\lambda_{n+1}-\lambda_n=0-0=0$ . Si 0 es no un valor propio de su gráfico, entonces $\lambda_n$ es el valor propio menos positivo de su gráfica, y $\lambda_{n+1}$ es su negativo. Así que estudiar $\lambda_n$ en este caso es de hecho equivalente a estudiar la diferencia $\lambda_n-\lambda_{n+1}=2\lambda_n$ .

Si además puede asumir otros supuestos sobre su grafo (por ejemplo, que tiene una única correspondencia perfecta... de nuevo, bastante razonable a partir de la teoría de Hueckel), entonces se puede decir más. Busca trabajos de Godsil, en particular su artículo "Inverses of Trees". Por ejemplo (a grandes rasgos), dado que cero no es un valor propio de tu grafo, aproximadamente derivado de la invertibilidad de la matriz de adyacencia está el límite $\lambda_m\leq \frac{1}{\lambda_1}$ con igualdad bajo cierta condición técnica en su grafo (una propiedad de tipo "autodual"). Para un límite inferior, Godsil muestra que $\lambda_n$ de cualquier grafo de este tipo está acotado a continuación por $\lambda_n$ de un grafo explícito construido en el artículo (es un producto corona de grafos, aunque él no utiliza esta terminología. De hecho, creo que es específicamente la corona $P_n\circ K_1$ que da el menor $\lambda_n$ entre dichos gráficos).

Espero que le sirva de ayuda.

Answer 2

Algo que puede resultarle útil es el Teorema del entrelazamiento de Cauchy .

En respuesta al comentario, es de suponer que el interés de Tomaz se centra en algunos tipos concretos de gráficos. Puede darse el caso de que un grafo de este tipo tenga algunos subgrafos bien comprendidos. Entonces se podría reducir la pregunta sobre el tamaño de los valores propios medios del grafo grande a una pregunta sobre el tamaño de los valores propios "aproximadamente medios" del grafo más pequeño.

Answer 3

Esto era demasiado largo para un comentario.

El trasfondo químico es básicamente el siguiente: un "sistema aromático" (cierto tipo de molécula) con 2n átomos de carbono tiene 2n "orbitales moleculares" donde pueden ir los electrones, cada uno de los cuales contiene dos electrones. Estos orbitales son combinaciones lineales de un "orbital atómico" de cada uno de los átomos de carbono, que casualmente se alinean de la forma correcta en que se combinan, y están repartidos por toda la molécula . (Sí, esto es una aproximación de los químicos a ciertas cosas de la mecánica cuántica).

Sus energías vienen dadas por los valores propios de la matriz de adyacencia (interpretados en las unidades correctas). Hay 2n electrones que irán en ellas. Dos electrones (con espines opuestos) pueden ir en cada orbital, y llenan los orbitales de menor a mayor energía. Así que los $n$ es la energía del orbital molecular de mayor ocupación (HOMO), y el $n+1$ st es la energía del orbital molecular más bajo desocupado (LUMO).

En particular, probablemente sea razonable suponer, a efectos químicos, que todos los vértices del grafo tienen grado 2 ó 3; piénsese en sistemas como las ilustradas en este artículo de Wikipedia .

Answer 4

Si se supone que el grafo es bipartito (como sugirió Cam) y $3-$ regular, entonces creo que los valores propios medios son siempre como máximo $\sqrt{2}$ en valor absoluto, siendo el gráfico de Heawood el único gráfico conexo con igualdad.

Sabemos que para cualquier número entero positivo $k$ el número de paseos cerrados en su gráfico de longitud $k$ es igual a $Tr(A^k)=\sum_i \lambda_i^k$ . En el caso $k=2$ se convierte en $$\sum_{i=1}^n \lambda_i^2 = 2 |E| = 3 n,$$ mientras que para $k=4$ tenemos $$\sum_{i=1}^n \lambda_i^4 \geq 15 n,$$ ya que hay $9n$ paseos cerrados de la forma $x \rightarrow y \rightarrow x \rightarrow z \rightarrow x$ (aquí $y$ posiblemente puede igualar $z$ ), y $6n$ paseos de la forma $x \rightarrow y \rightarrow z \rightarrow y \rightarrow x$ donde $z \neq x$ .

Supongamos ahora que $\lambda_i^2 \in [t, 9]$ para cada $i$ . De la convexidad se deduce que, sujeto a la restricción $\sum \lambda_i^2=3n$ la suma de $\lambda_i^4$ se maximiza cuando cada $\lambda_i^2$ es $t$ o $9$ es decir $$\sum_{i=1}^n \lambda_i^4 \leq (\frac{3-t}{9-t} n) (81) + (\frac{6}{9-t} n) (t^2)=(27-6t)n.$$

Comparando con nuestro límite inferior, vemos $t \leq 2$ . La igualdad sólo puede mantenerse cuando hay exactamente $n/7$ valores propios iguales a $3$ en valor absoluto, y el resto igual a $\sqrt{2}$ en valor absoluto. Este es el espectro de $n/14$ copias disjuntas del grafo de Heawood, que está determinado unívocamente por su espectro.

Parece que debería haber una forma de decir que los grafos conectados grandes tienen un valor propio mucho menor que éste, pero no veo cómo modificar este método para demostrarlo (no estoy seguro de cómo se mostraría la conectividad del grafo en el recuento de caminos). Si su gráfico tiene muchos $4$ puede incluirlos en el $k=4$ límite inferior para obtener un límite mejor en $t$ .

Answer 5

En primer lugar, en lo que respecta a las matemáticas del problema del valor propio medio, existen resultados para el caso de un grafo G con un único emparejamiento perfecto, especialmente si además el grafo es bipartito. Véase D. J. Klein & A. Misra, Croat. Chim. Acta 77 (2002) 179-191, donde se realiza una transformación (llamada "Kekulean") de un grafo original G con una única correspondencia perfecta a otro grafo G' con pesos de arista con signo tal que la matriz de adyacencia A(G') es la inversa de la original A(G). Se identifican circunstancias en las que los signos de G' pueden eliminarse para dejar un grafo ordinario sin signos G" con valores propios inversos a los de G. Se encuentran otras circunstancias en las que G y G" son isomorfos. Las técnicas para tratar con valores propios máximos (de A(G') o A(G")) se utilizan para dar información sobre los valores propios "medios" (de A(G)).

En segundo lugar, cabe hacer algunos comentarios sobre el contexto químico. Los valores propios de la matriz de adyacencia más próximos a 0 se tienen muy en cuenta en química, ya que localizan los electrones más fácilmente excitables y la diferencia de valores propios para los valores propios medios proporciona una medida adecuada de la energía necesaria para la excitación. Más detalladamente, los valores propios de la matriz de adyacencia proporcionan estimaciones aproximadas (teóricas de Huckel) de las energías de 1 electrón para los electrones pi de las redes de carbono conjugado, ya que los otros electrones están en su mayor parte más fuertemente ligados. Una energía completa de N electrones no es más que una suma de energías de 1 electrón, cada una de ellas multiplicada por un número de ocupación n(e) para ese valor propio e: los números de ocupación toman los valores 0, 1 ó 2 y suman N. Para una red de carbono conjugado eléctricamente neutra (como es habitual), el número total N de tales electrones coincide con el número de sitios. Entonces el estado de N electrones más favorecido para N=par tiene los N/2 eigenvalores más grandes e cada uno con n(e)=2 y todos los demás eigenvalores e' con n(e')=0. Para impar N=2k+1, los k e más grandes tienen n(e)=2, el siguiente eigenvalor más bajo e' tiene n(e')=1, y los k eigenvalores más bajos restantes e" tienen n(e")=0. La brecha de interés es la menor diferencia de energía entre un nivel no doblemente ocupado y otro no vacío. [Un punto de confusión potencial es que los eigenvalores de 1 electrón son proporcionales a los eigenvalores con una proporcionalidad que es negativa; entonces la circunstancia favorable ("estado básico") de ocupar los eigenvalores mayores corresponde a ocupar los niveles de 1 electrón de menor energía]. De todo este comentario se desprende que para los grafos bipartitos los valores propios "medios" de interés son los más próximos a 0, mientras que para los grafos no bipartitos esto no es necesariamente así. Los grafos químicos de interés para las redes de carbono conjugado tienen vértices sólo de grados 1, 2 ó 3.