Spectral graph theory

In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix.

An undirected graph has a symmetric adjacency matrix and therefore has real eigenvalues (the multiset of which is called the graph's spectrum) and a complete set of orthonormal eigenvectors.

While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant.

Spectral graph theory is also concerned with graph parameters that are defined via multiplicities of eigenvalues of matrices associated to the graph, such as the Colin de Verdière number.

Isospectral graphs

Two graphs are called isospectral or cospectral if the adjacency matrices of the graphs have equal multisets of eigenvalues.

Two isospectral enneahedra, the smallest possible isospectral polyhedral graphs

Isospectral graphs need not be isomorphic, but isomorphic graphs are always isospectral. The smallest pair of nonisomorphic cospectral undirected graphs is {K1,4, C4 U K1}, comprising the 5-vertex star and the graph union of the 4-vertex cycle and the single-vertex graph, as reported by Collatz and Sinogowitz[1][2] in 1957. The smallest pair of nonisomorphic cospectral polyhedral graphs are enneahedra with eight vertices each.[3]

Almost all trees are cospectral, i.e., the share of cospectral trees on n vertices tends to 1 as n grows.[4]

Isospectral graphs can also be constructed by means of the Sunada method.[5]

Another important source of isospectral graphs are the point-collinearity graphs and the line-intersection graphs of point-line geometries. These graphs are always isospectral but are often non-isomorphic.[6]

Cheeger inequality

The famous Cheeger's inequality from Riemannian geometry has a discrete analogue involving the Laplacian matrix; this is perhaps the most important theorem in spectral graph theory and one of the most useful facts in algorithmic applications. It approximates the sparsest cut of a graph through the second eigenvalue of its Laplacian.

Cheeger constant

The Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: for example, constructing well-connected networks of computers, card shuffling, and low-dimensional topology (in particular, the study of hyperbolic 3-manifolds).

More formally, the Cheeger constant h(G) of a graph G on n vertices is defined as

h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial(S)|}{|S|},

where the minimum is over all nonempty sets S of at most n/2 vertices and ∂(S) is the edge boundary of S, i.e., the set of edges with exactly one endpoint in S.[7]

Cheeger inequality

When the graph G is d-regular, there is a relationship between h(G) and the spectral gap d − λ2 of G. An inequality due to Tanner and independently Alon and Milman[8] states that[9]

\tfrac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}.

This inequality is closely related to the Cheeger bound for Markov chains and can be seen as a discrete version of Cheeger's inequality in Riemannian geometry.

Historical outline

Spectral graph theory emerged in the 1950s and 1960s. Besides graph theoretic research on the relationship between structural and spectral properties of graphs, another major source was research in quantum chemistry, but the connections between these two lines of work were not discovered until much later.[10] The 1980 monograph Spectra of Graphs[11] by Cvetković, Doob, and Sachs summarised nearly all research to date in the area. In 1988 it was updated by the survey Recent Results in the Theory of Graph Spectra.[12] The 3rd edition of Spectra of Graphs (1995) contains a summary of the further recent contributions to the subject.[10] Discrete geometric analysis created and developed by Toshikazu Sunada in the 2000s deals with spectral graph theory in terms of discrete Laplacians associated with weighted graphs,[13] and finds application in various fields, including shape analysis.

See also

References

  1. ↑ Collatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63–77, 1957.
  2. ↑ Weisstein, Eric W., "Cospectral Graphs", MathWorld.
  3. ↑ Hosoya, Haruo; Nagashima, Umpei; Hyugaji, Sachiko (1994), "Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices", Journal of Chemical Information and Modeling 34 (2): 428–431, doi:10.1021/ci00018a033.
  4. ↑ Schwenk, A. J. "Almost All Trees are Cospectral" In: New Directions in the Theory of Graphs (F. Harary, Ed.), Academic Press, New York, 1973, pp. 275–307.
  5. ↑ Sunada, Toshikazu (1985), "Riemannian coverings and isospectral manifolds", Ann. of Math. 21: 169–186.
  6. ↑ Brouwer, Andries; Haemers, Willem H. (2011). "Spectra of Graphs" (PDF).
  7. ↑ Definition 2.1 in Hoory, Linial & Widgerson (2006)
  8. ↑ Alon & Spencer 2011.
  9. ↑ Theorem 2.4 in Hoory, Linial & Widgerson (2006)
  10. 1 2 Eigenspaces of Graphs, by Dragoš Cvetković, Peter Rowlinson, Slobodan Simić (1997) ISBN 0-521-57352-1
  11. ↑ Dragoš M. Cvetković, Michael Doob, Horst Sachs, Spectra of Graphs (1980)
  12. ↑ Cvetković, Dragoš M.; Doob, Michael; Sachs, Horst; Torgasev, A. (1988). Recent Results in the Theory of Graph Spectra. Annals of Discrete mathematics. ISBN 0-444-70361-6.
  13. ↑ Sunada, Toshikazu (2008), "Discrete geometric analysis", Proceedings of Symposia in Pure Mathematics 77: 51–86.

External links

This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.