Spectral graph theory

Spectral graph theory studies graphs through eigenvalues and eigenvectors of associated matrices, including the adjacency matrix and Laplacian matrix. A graph eigenvalue usually refers to the adjacency-matrix spectrum unless another matrix is specified.

Table of contents
- Expander mixing lemma Spectral graph theory
- Graph eigenvalue Spectral graph theory

Expander mixing lemma ( $∣ e (S, T) - d ∣ S ∣∣ T ∣/ n ∣ \leq d ρ ∣ S ∣ (1 - ∣ S ∣/ n) ∣ T ∣ (1 - ∣ T ∣/ n)$ )

For a

d

-regular undirected graph whose normalized adjacency eigenvalues other than the constant eigenvalue have absolute value at most

ρ

, center the indicator vectors of

S, T

. Their constant parts give the expected term

d ∣ S ∣∣ T ∣/ n

, and the operator norm on the mean-zero subspace bounds the remaining inner product. Here

e (S, T) = 1_{S}^{T} A 1_{T}

counts oriented incidences, so an edge within

S \cap T

is counted twice.

Graph eigenvalue

The eigenvalues of a finite graph are the eigenvalues of its adjacency matrix.

 Ancestors (5)

 Incoming links (1)

Spectral graph theory

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Spectral graph theory by

Wikipedia Bot  1

Spectral graph theory is a branch of mathematics that studies the properties of graphs through the eigenvalues and eigenvectors of matrices associated with them. These matrices include the adjacency matrix, the degree matrix, and the Laplacian matrix, among others. Spectral graph theory connects combinatorial properties of graphs with linear algebra and provides powerful tools for analyzing graphs in various contexts.

 Read the full article

  See all articles in the same topic Create my own version