El medio autovalores de un grafo no dirigido

Question

Deje $ \lambda_1 \ge \lambda_2 \ge \dots \lambda_{2n} $ la obtención de los valores propios de una matriz de adyacencia de un grafo no dirigido a $G$ $2n$ vértices. Estoy en busca de cualquier trabajo o referencias que se considera el medio autovalores $\lambda_n$$\lambda_{n+1}$. En particular, los límites en las $R(G) = max(|\lambda_n|,|\lambda_{n+1}|)$ son bienvenidos.

Por ejemplo, un equipo de búsqueda mostraron que la mayoría conectado gráficas con el máximo de valencia 3 $R(G) \le 1$. La única excepción conocida es la Heawood gráfico.

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

Edit: Nota de que en la fórmula original de $R(G)$ el valor absoluto de los signos que faltaban.

Answer 1

Si usted asume el grafo es bipartito (Cam sugerido) y $3-$regular, entonces creo que el medio autovalores son siempre en la mayoría de las $\sqrt{2}$ en valor absoluto, con la Heawood gráfico de ser la única gráfica conectada con la igualdad.

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

Ahora supongamos que $\lambda_i^2 \in [t, 9]$ por cada $i$. Se sigue de convexidad que, sujeto a la restricción $\sum \lambda_i^2=3n$, la suma de $\lambda_i^4$ se maximiza cuando todos los $\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 a $t \leq 2$. La igualdad sólo puede contener cuando hay exactamente $n/7$ autovalores igual a $3$ en valor absoluto, y el resto igual a $\sqrt{2}$ en valor absoluto. Este es el espectro de $n/14$ copias disjuntas de la Heawood gráfico, que está determinada únicamente por su espectro.

Se siente como debería haber una forma de decir que las grandes conectado gráficos tienen un autovalor mucho más pequeño que este, pero no veo cómo modificar este método para demostrar que (no estoy seguro de cómo la conectividad de la gráfica se mostrará en la ruta de acceso de la cuenta). Si el gráfico tiene muchas $4$ ciclos, puede incluirlas en el $k=4$ límite inferior para obtener una mejor obligado en $t$.

Answer 2

Si el grafo es bipartito (natural de restricción si la motivación viene de Hueckel teoría), entonces la simetría del espectro indica un muy buen negocio. Si 0 es un valor propio de su gráfica, entonces es un doble valor propio, y por lo $\lambda_{n+1}-\lambda_n=0-0=0$. Si es 0 no es un valor propio de el gráfico, a continuación, $\lambda_n$ es el mínimo autovalor positivo de su gráfica, y $\lambda_{n+1}$ es de su negativa. Para el estudio de $\lambda_n$ en este caso es de hecho equivalente para el estudio de la diferencia de $\lambda_n-\lambda_{n+1}=2\lambda_n$.

Si usted puede también asumir algunos otros supuestos en el gráfico (por ejemplo, que tiene un único perfecto maridaje...de nuevo, bastante razonable de Hueckel teoría), entonces más se puede decir. Buscar obras de Godsil, en particular, su artículo "los Inversos de los Árboles." Por ejemplo (aproximadamente), ya que el cero no es un valor propio de su gráfico, aproximadamente derivados de la invertibility de la matriz de adyacencia es la obligada $\lambda_m\leq \frac{1}{\lambda_1}$, con igualdad bajo ciertas condiciones técnicas en el gráfico de ("dual"ish tipo de propiedad). Para el límite inferior, Godsil muestra que $\lambda_n$ de cualquier gráfico está acotado abajo por $\lambda_n$ explícita de una gráfica construida en el papel (es una corona de producto de los gráficos, a pesar de que él no utiliza esta terminología. De hecho, creo que es específicamente la corona $P_n\circ K_1$, lo que le da la más baja posible de la $\lambda_n$ entre los gráficos de este tipo).

Espero que ayude.

Answer 3

En primer lugar, con respecto a las matemáticas de la media autovalor problema hay resultados para el caso de un grafo G con solo un perfecto maridaje, especialmente si también el grafo es bipartito. Véase D. J. Klein & A. Misra, Croata. Chim. Acta 77 (2002) 179-191, donde una transformación (llamado "Kekulean") a partir de un original de google con un solo ideal de que se elijan a otro grafo G' firmado con borde de pesos tales que la matriz de adyacencia A(G') es la inversa de la original de Una(G). Las circunstancias son identificados, donde los signos en G' puede ser eliminado para dejar un ordinario sin signo gráfico G" todavía con autovalores inversa a los de G. Además se encuentran circunstancias donde G & G" son isomorfos. Técnicas para tratar con el máximo de autovalores (de(G') o(G)) se usan para dar información sobre el "medio" autovalores (de A(G)).

En segundo lugar, algunos comentarios pueden ser realizadas en el contexto químico. La adyacencia de la matriz de autovalores más cercano a 0 se considera como en la química, ya que busque los electrones más fácilmente excitado y el autovalor diferencia por medio autovalores da una medida adecuada de la energía necesaria para la excitación. En más detalle, los autovalores de la matriz de adyacencia de proporcionar crudo (Huckel-teórico) las estimaciones de 1-energías de electrones para la pi-los electrones de los conjugados de carbono redes -- los demás electrones para la mayoría de la parte más estrechamente vinculados. Un total de N-la energía de los electrones es sólo una suma de más de 1-energías de electrones de cada uno, multiplicado por una ocupación número n(e) para que autovalor e -- la ocupación de los números de tomar los valores 0, 1, o 2, y sumando a N. Para eléctricamente neutro conjugado de emisiones de carbono de la red (como es una circunstancia común), el número total N de tales electrones coincide con el número de sitios. A continuación, el más favorecido de electrones N estado para N=incluso tiene los N/2 mayores valores propios de e cada una con n(e)=2 y todos los demás valores propios e' con n(e')=0. Para impar N=2k+1, k más grande e tiene n(e)=2, el menor autovalor e' tiene n(e')=1, y el k restante inferior autovalores e" tiene n(e")=0. La brecha de interés es el que menos diferencia de energía entre un nivel que no es doblemente ocupado y otra vacía. [Un punto de confusión es que el 1 de electrones autovalores son proporcionales a los valores propios con un proporcionalidad, que es negativo; luego de la favorable ("tierra-estado") por la circunstancia de que se ocupa de los mayores valores propios corresponde a ocupar el de menor energía de electrones 1 niveles.] De todo este comentario se puede observar que para grafos bipartitos el "medio" autovalores de interés son los más cercanos a 0, mientras que para nonbipartite gráficos esto no es necesariamente así. La química de los gráficos de interés para el conjugado de carbono redes tienen vértices sólo de grados 1, 2, o 3.

Answer 4

Una cosa que usted puede encontrar útil es la de Cauchy entrelazado teorema.

En respuesta al comentario, presumiblemente Tomaz interés está en algún determinado tipo de gráficos. Puede darse el caso de que una gráfica tiene algunos bien entendido subdiagramas. Entonces se podría reducir a la pregunta sobre el tamaño de la media de los autovalores de la gran gráfico a una pregunta sobre el tamaño de la "aproximadamente la mitad" valores propios " de los más pequeños en el gráfico.

Answer 5

Esto era demasiado largo para un comentario.

La química de fondo es básicamente esto: un "sistema aromático" (un tipo de molécula) con 2n átomos de carbono tiene 2n "orbitales moleculares", donde los electrones pueden ir, cada uno de los cuales tiene dos electrones. Estos orbitales son combinaciones lineales de un "atómico orbital" de cada uno de los átomos de carbono, que suceden a la línea en la forma correcta de combinar, y se extienden sobre toda la molécula . (Sí, este es un químico de la aproximación a ciertas cosas en la mecánica cuántica.)

Sus energías están dadas por los valores propios de la matriz de adyacencia (interpretado en el derecho de unidades). Hay 2n electrones que van en ellos. Dos electrones con espines opuestos) puede ir en cada orbital, y llenan los orbitales de energía más baja a la más alta. Por lo que el $n$th autovalor es la energía del orbital molecular más alto ocupado (HOMO), y el $n+1$st es la energía del orbital molecular más bajo desocupado (LUMO).

En particular, es probablemente razonable suponer para la industria química a los efectos de que todos los vértices del grafo tienen un grado 2 o 3; pensar en sistemas como los que se ilustra en este artículo de la Wikipedia.