Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
I would be very curious to hear more about the chemistry background as well. In addition: can you be more specific about which aspects of $R(G)$ you are interested in? Am I right in supposing you want bounds on $R(G)$ as a function of the largest degree of a graph? –  alex Mar 6 '10 at 5:25
2  
If you google for HOMO LUMO gap you get over 65000 hits. The first one is Wikipeadia: en.wikipedia.org/wiki/HOMO/LUMO. The difference is the minimal energy needed to excite a molecule from the the ground state to an excited state. The at each energy level the eigenvector is viewed as a molecular orbital. Yes, we do have some upper bounds of $R(G)$ depending on the largest valence of a graph but we do not know how sharp they are. –  Tomaž Pisanski Mar 6 '10 at 9:30
1  
What sort of bounds do you know/expect for fullerenes? –  Douglas Zare Mar 6 '10 at 14:42
1  
Computer search shows that for small fullerenes $R < 1$ –  Tomaž Pisanski Mar 7 '10 at 2:25
1  
Hsien-Chih: In general $R(G)$ is bounded by a square root if the average valence of $G$. This will appear in the paper "P. W. Fowler, T. Pisanski: HOMO–LUMO Maps for Chemical Graphs, MATCH - Communicantions in mathematical and computer chemistry, Volume 64 (2010) number 2 pp. 373-390". Motivation for my question comes from the fact that a lot is known about the largest, second largest and the smallest eigenvalue, but I am not familiar about results on the middle eigenvalues of a positive symmetric matrix. –  Tomaž Pisanski Mar 11 '10 at 8:37

5 Answers 5

up vote 6 down vote accepted

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.

share|improve this answer
3  
Hmm. Can you explain why this is an answer to the question? –  Mariano Suárez-Alvarez Mar 6 '10 at 3:30
    
Sorry, I am new to MathOverflow and may have checked the answer too soon, but I ma sure it is definitely a step in the right direction. –  Tomaž Pisanski Mar 6 '10 at 8:19

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.

share|improve this answer
    
Cam: Thanks for spotting the missing absolute value signs, and thanks for your suggestions! –  Tomaž Pisanski Mar 12 '10 at 18:49
    
Sure thing. Nice question. –  Cam McLeman Mar 13 '10 at 21:40

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.

share|improve this answer
3  
One interesting possibility would be to consider the case where the "hexagonal tiling" region is large relative to the rest of the stuff. Then somehow figure out the rough distribution of the eigenvalues for large hexagonal graphs, and then apply interlacing. –  Noah Snyder Mar 6 '10 at 17:35
    
Noah, that's not a bad idea, although I'm not sure if the "hexagonal tiling" region ever gets that large in practice. –  Michael Lugo Mar 12 '10 at 17:30

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$.

share|improve this answer
    
Why is it true that every $\lambda_i^2$ is either $t$ or $9$? It seems like its possible that $\sum_i \lambda_i^2 = 3n$ has no solution at all if we require each $\lambda_i^2 \in \{ t, 9\}$. –  alex Mar 15 '10 at 20:18
    
The point is that any actual solution has $\sum \lambda_i^4$ at least as large as the hypothetical (perhaps noninteger) solution I wrote down. To put it differently, what I'm doing is taking the inequality $(x t^2+(1-x)9^2 \geq (xt+(1-x)9)^2$, then for each $i$ choosing an appropriate $x$ so that the right hand side is $(\lambda_i^2)^2$. Adding up over all $i$ then gives the same bound. –  Kevin P. Costello Mar 15 '10 at 22:08

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.