The middle eigenvalues of an undirected graph - MathOverflow

The middle eigenvalues of an undirected graph

2010-03-06T00:51:20Z

Let $ \lambda_1 \ge \lambda_2 \ge \dots \lambda_{2n} $ be the collection of eigenvalues of an adjacency matrix of an undirected graph $G$ on $2n$ vertices. I am looking for any work or references that would consider the middle eigenvalues $\lambda_n$ and $\lambda_{n+1}$. In particular, the bounds on $R(G) = max(|\lambda_n|,|\lambda_{n+1}|)$ are welcome.

For instance, a computer search showed that most connected graphs with maximum valence 3 have $R(G) \le 1$. The only known exception is the Heawood graph.

Motivation for this question comes from theoretical chemistry, where the difference $\lambda_n-\lambda_{n+1}$ in Hueckel theory is called the HOMO-LUMO gap.

Edit: Note that in the original formula for $R(G)$ the absolute value signs were missing.

Answer by Noah Snyder for The middle eigenvalues of an undirected graph

2010-03-06T01:45:42Z

One thing that you might find useful is the Cauchy interlacing theorem.

In response to the comment, presumably Tomaz's interest is in some particular sorts of graphs. It may be the case that such a graph has some well-understood subgraphs. Then you could reduce the question about the size of the middle eigenvalues of the big graph to a question about the size of the "approximately middle" eigenvalues of the smaller graph.

Answer by Michael Lugo for The middle eigenvalues of an undirected graph

2010-03-06T13:06:15Z

This was too long for a comment.

The chemistry background is basically this: an "aromatic system" (a certain type of molecule) with 2n carbon atoms has 2n "molecular orbitals" where electrons can go, each of which holds two electrons. These orbitals are linear combinations of one "atomic orbital" from each of the carbon atoms, which happen to line up in the right way that they combine, and are spread out over the entire molecule . (Yes, this is a chemist's approximation to certain things in quantum mechanics.)

Their energies are given by the eigenvalues of the adjacency matrix (interpreted in the right units). There are 2n electrons that will go in them. Two electrons (with opposite spins) can go in each orbital, and they fill the orbitals from lowest energy to highest. So the $n$th eigenvalue is the energy of the highest occupied molecular orbital (HOMO), and the $n+1$st is the energy of the lowest unoccupied molecular orbital (LUMO).

In particular, it is probably reasonable to assume for chemical purposes that all the vertices of the graph have degree 2 or 3; think of systems like the ones illustrated in this Wikipedia article.

Answer by Cam McLeman for The middle eigenvalues of an undirected graph

2010-03-12T15:38:04Z

If your graph is bipartite (a natural restriction if the motivation comes from Hueckel theory), then the symmetry of the spectrum tells you a pretty good deal. If 0 is an eigenvalue of your graph, then it is a double eigenvalue, and so $\lambda_{n+1}-\lambda_n=0-0=0$. If 0 is not an eigenvalue of your graph, then $\lambda_n$ is the least positive eigenvalue of your graph, and $\lambda_{n+1}$ is its negative. So studying $\lambda_n$ in this case is in fact equivalent to studying the difference $\lambda_n-\lambda_{n+1}=2\lambda_n$.

If you can also assume some other assumptions on your graph (e.g., that it has a unique perfect matching...again, fairly reasonable from Hueckel theory), then more can be said. Look up works by Godsil, in particular his paper "Inverses of Trees." For example (roughly), since zero is not an eigenvalue of your graph, roughly stemming from the invertibility of the adjacency matrix is the bound $\lambda_m\leq \frac{1}{\lambda_1}$, with equality under a certain technical condition on your graph (a "self-dual"ish type property). For a lower bound, Godsil shows that $\lambda_n$ of any such graph is bounded below by $\lambda_n$ of an explicit graph constructed in the paper (it is a corona product of graphs, though he doesn't use this terminology. In fact, I think it's specifically the corona $P_n\circ K_1$ which gives the lowest possible $\lambda_n$ among such graphs).

Hope that helps.

Answer by Kevin P. Costello for The middle eigenvalues of an undirected graph

2010-03-15T17:28:16Z

If you assume the graph is bipartite (as Cam suggested) and $3-$regular, then I believe the middle eigenvalues are always at most $\sqrt{2}$ in absolute value, with the Heawood graph being the only connected graph with equality.

We know that for any positive integer $k$ the number of closed walks on your graph of length $k$ is equal to $Tr(A^k)=\sum_i \lambda_i^k$. In the case $k=2$, this becomes $$\sum_{i=1}^n \lambda_i^2 = 2 |E| = 3 n,$$ while for $k=4$ we have $$\sum_{i=1}^n \lambda_i^4 \geq 15 n,$$ since there are $9n$ closed walks of the form $x \rightarrow y \rightarrow x \rightarrow z \rightarrow x$ (here $y$ possibly can equal $z$), and $6n$ walks of the form $x \rightarrow y \rightarrow z \rightarrow y \rightarrow x$ where $z \neq x$.

Now suppose that $\lambda_i^2 \in [t, 9]$ for every $i$. It follows from convexity that, subject to the constraint $\sum \lambda_i^2=3n$, the sum of $\lambda_i^4$ is maximized when every $\lambda_i^2$ is either $t$ or $9$, that is to say $$\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.$$

Comparing with our lower bound, we see $t \leq 2$. Equality can only hold when there are exactly $n/7$ eigenvalues equal to $3$ in absolute value, and the rest equal to $\sqrt{2}$ in absolute value. This is the spectrum of $n/14$ disjoint copies of the Heawood graph, which is uniquely determined by its spectrum.

It feels like there should be a way of saying that large connected graphs have an eigenvalue much smaller than this, but I don't see how to modify this method to show that (I'm not sure how the connectedness of the graph would show up in path counting). If your graph has many $4$ cycles, you can include them in the $k=4$ lower bound to get a better bound on $t$.

Answer by douglas-klein for The middle eigenvalues of an undirected graph

2010-08-16T22:12:19Z

First, regarding the mathematics of the middle-eigenvalue problem there are results for the case of a graph G with just a single perfect matching, especially if also the graph is bipartite. See D. J. Klein & A. Misra, Croat. Chim. Acta 77 (2002) 179-191, where a transform (called "Kekulean") from an original G with a single perfect matching is made to another graph G' with signed edge weights such that the adjacency matrix A(G') is the inverse of the original A(G). Circumstances are identified where the signs on G' may be eliminated to leave an ordinary unsigned graph G" still with eigenvalues inverse to those of G. Further circumstances are found where G & G" are isomorphic. Techniques for dealing with maximum eigenvalues (of A(G') or A(G")) are used to give information on the "middle" eigenvalues (of A(G)).

Second, some comments might be made on the chemical context. The adjacency-matrix eigenvalues nearest 0 are much considered in chemistry, as they locate the electrons most easily excited and the eigenvalue difference for middle eigenvalues gives an appropriate measure of the energy needed for excitation. In more detail, the eigenvalues of the adjacency matrix provide crude (Huckel-theoretic) estimates of 1-electron energies for the pi-electrons of conjugated carbon networks -- the other electrons being for the most part more tightly bound. A full N-electron energy is then just a sum over 1-electron energies each multiplied by an occupation number n(e) for that eigenvalue e -- the occupation numbers taking values 0, 1, or 2 and summing to N. For an electrically neutral conjugated-carbon network (as is a common circumstance), the total number N of such electrons matches the number of sites. Then the most favored N-electron state for N=even has the N/2 largest eigenvalues e each with n(e)=2 and all other eigenvalues e' with n(e')=0. For odd N=2k+1, the k largest e have n(e)=2, the next lowest eigenvalue e' has n(e')=1, and the k remaining lower eigenvalues e" have n(e")=0. The gap of interest is the least energy difference between a level not doubly occupied and another not empty. [A point of potential confusion is that the 1-electron eigenvalues are proportional to the eigenvalues with a proportionality which is negative; then the favorable ("ground-state") circumstance of occupying the largest eigenvalues corresponds to occupying the lowest energy 1-electron levels.] From all this commentary it can be seen that for bipartite graphs the "middle" eigenvalues of interest are those nearest 0, while for nonbipartite graphs this is not necessarily so. The chemical graphs of interest for conjugated-carbon networks have vertices just of degrees 1, 2, or 3.