11 - Nontrees

Summary

Introduction and Observations

The problem of multiplicity lists for Hermitian matrices is remarkably different when the underlying graph G is not a tree. Some highly algebraic aspects of the problem are the same. For example,

• Maximum multiplicity in H(G) corresponds to minimum rank in H(G).

• Multiplicity can change by at most 1 when a vertex is removed.

• Multiplicity can change under perturbation by at most the rank of the perturbation.

• Many of the results on perturbation of diagonal entries (Section 4.1) are the same.

However, as seen in Chapter 2, there is little vestige of the technology of Parter vertices for general graphs, and it maywell be that all vertices are downers, even when multiple eigenvalues are present. Two of the construction techniques we have described in Chapter 7 are almost not available, and the third, the IFT, is more problematic to carry out. The similarities above are too weak to be very helpful, and minimum rank for general graphs is known to be very subtle, while it has a lovely answer for trees. Thus, determination of possible multiplicities is even more difficult for general graphs and often involves looking at very particular cases.

There are some things that have been said, or can be said, and we review a selection of them here.

The Complete Graph

The complete graph K_n on n ≥ 2 vertices is relatively easy to analyze, as it allows many multiplicity lists. However, it requires different techniques to verify that various spectra occur, and these techniques are useful for other dense graphs that we pursue in Section 11.7. One list that K_n obviously does not allow is just one eigenvalue of multiplicity n. An Hermitian matrix with this list would be similar to, and thus, equal to, a multiple of I. It would be diagonal and thus is allowed only by the trivial graph with n vertices and no edges.