EUVIMEDEUVIMED entdecken
Crossref

Review of Spectral Graph Theory

Jacob Lurie

ACM SIGACT News · 1999-06 · 30 (2) · 14-16

DOI: 10.1145/568547.568553 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM SIGACT News, 1999-06. Verfasst von Jacob Lurie. Die Arbeit wurde bisher 37-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Specifying a graph is equivalent to specifying its adjacency relation, which may be encoded in the form of a matrix. This suggests that study of the adjacency matrix from a linear-algebraic point of view might yield valuable information about graphs. In particular, any invariant associated to the matrix is also an invariant associated to the graph, and might have combinatorial meaning. Spectral graph theory is the study of the relationship between a graph and the eigenvalues of matrices (such as the adjacency matrix) naturally associated to that graph. This book looks at the subject from a geometric point of view, exploiting an analogy between a graph and a Riemannian manifold: Chung defines the Laplacian of a graph, a matrix closely related to the adjacency matrix, in analogy with the continuous case and studies the eigenvalues of this Laplacian.There are several reasons that these eigenvalues may be of interest. On the purely mathematical level, the eigenvalues have the advantage of being an extremely natural invariant which behaves nicely under operations such as Cartesian product and disjoint union. From a combinatorial point of view, the eigenvalues of a graph are related to many other more "discrete" invariants. From a geometric point of view, there are many respects in which the eigenvalues of a graph behave like the spectrum of a compact Riemannian manfiold. For the computationally-minded, the eigenvalues of a graph are easy to compute, and their relationship to other invariants can often yields good approximations to less tractible computations.

Zitieren

APA

Lurie, J. (1999). Review of Spectral Graph Theory. ACM SIGACT News, 30(2), 14-16. https://doi.org/10.1145/568547.568553

Vancouver

Lurie J. Review of Spectral Graph Theory. ACM SIGACT News. 1999;30(2):14-16. doi:10.1145/568547.568553

BibTeX
@article{Lurie1999,
  author = {Lurie, Jacob},
  title = {Review of Spectral Graph Theory},
  journal = {ACM SIGACT News},
  year = {1999},
  volume = {30},
  number = {2},
  pages = {14--16},
  doi = {10.1145/568547.568553}
}
Kostenlos starten →