In
mathematics, spectral
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
is the study of the properties of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
in relationship to the
characteristic polynomial,
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted ...
s, and
eigenvector
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted ...
s of matrices associated with the graph, such as its
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
or
Laplacian matrix.
The adjacency matrix of a simple undirected graph is a
real
Real may refer to:
Currencies
* Brazilian real (R$)
* Central American Republic real
* Mexican real
* Portuguese real
* Spanish real
* Spanish colonial real
Music Albums
* ''Real'' (L'Arc-en-Ciel album) (2000)
* ''Real'' (Bright album) (2010) ...
symmetric matrix
In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally,
Because equal matrices have equal dimensions, only square matrices can be symmetric.
The entries of a symmetric matrix are symmetric with ...
and is therefore
orthogonally diagonalizable; its eigenvalues are real
algebraic integer
In algebraic number theory, an algebraic integer is a complex number which is integral over the integers. That is, an algebraic integer is a complex root of some monic polynomial (a polynomial whose leading coefficient is 1) whose coefficients ...
s.
While the adjacency matrix depends on the vertex labeling, its
spectrum
A spectrum (plural ''spectra'' or ''spectrums'') is a condition that is not limited to a specific set of values but can vary, without gaps, across a continuum. The word was first used scientifically in optics to describe the rainbow of colors ...
is a
graph invariant
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
* Graph (topology), a topological space resembling a graph in the sense of discr ...
, although not a complete one.
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.
Cospectral graphs
Two graphs are called cospectral or isospectral if the adjacency matrices of the graphs are
isospectral
In mathematics, two linear operators are called isospectral or cospectral if they have the same spectrum. Roughly speaking, they are supposed to have the same sets of eigenvalues, when those are counted with multiplicity.
The theory of isospectr ...
, that is, if the adjacency matrices have equal
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
s of eigenvalues.
![Isospectral enneahedra](https://upload.wikimedia.org/wikipedia/commons/c/c7/Isospectral_enneahedra.svg)
Cospectral graphs need not be
isomorphic, but isomorphic graphs are always cospectral.
Graphs determined by their spectrum
A graph
is said to be determined by its spectrum if any other graph with the same spectrum as
is isomorphic to
.
Some first examples of families of graphs that are determined by their spectrum include:
* The
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
s.
* The finite
starlike trees.
Cospectral mates
A pair of graphs are said to be cospectral mates if they have the same spectrum, but are non-isomorphic.
The smallest pair of cospectral mates is , comprising the 5-vertex
star and the
graph union
In the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary (one input) and binary (two input) operations.
Unary operations
Unary operations create a new graph f ...
of the 4-vertex
cycle and the single-vertex graph, as reported by Collatz and Sinogowitz in 1957.
The smallest pair of
polyhedral cospectral mates are
enneahedra with eight vertices each.
Finding cospectral graphs
Almost all tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
s are cospectral, i.e., as the number of vertices grows, the fraction of trees for which there exists a cospectral tree goes to 1.
A pair of
regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegr ...
s are cospectral if and only if their complements are cospectral.
A pair of
distance-regular graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and .
...
s are cospectral if and only if they have the same intersection array.
Cospectral graphs can also be constructed by means of the
Sunada method.
Another important source of cospectral graphs are the point-collinearity graphs and the line-intersection graphs of
point-line geometries. These graphs are always cospectral but are often non-isomorphic.
Cheeger inequality
The famous
Cheeger's inequality from
Riemannian geometry
Riemannian geometry is the branch of differential geometry that studies Riemannian manifolds, smooth manifolds with a ''Riemannian metric'', i.e. with an inner product on the tangent space at each point that varies smoothly from point to point ...
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
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
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
Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome.
__TOC__
Techniques
Overh ...
, and
low-dimensional topology
In mathematics, low-dimensional topology is the branch of topology that studies manifolds, or more generally topological spaces, of four or fewer dimensions. Representative topics are the structure theory of 3-manifolds and 4-manifolds, knot th ...
(in particular, the study of
hyperbolic
Hyperbolic is an adjective describing something that resembles or pertains to a hyperbola (a curve), to hyperbole (an overstatement or exaggeration), or to hyperbolic geometry.
The following phenomena are described as ''hyperbolic'' because they ...
3-
manifolds).
More formally, the Cheeger constant ''h''(''G'') of a graph ''G'' on ''n'' vertices is defined as
:
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''.
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 Dodziuk and independently
Alon Alon or ALON may refer to:
* Alon (name), an Israeli given name and surname
* Alon, Mateh Binyamin, an Israeli settlement in the West Bank
* Alon Inc, an American airplane builder, known for the Alon A-4
* Alon USA, an American energy company
* Alu ...
and
Milman states that
:
This inequality is closely related to the
Cheeger bound In mathematics, the Cheeger bound is a bound of the second largest eigenvalue of the transition matrix of a finite-state, discrete-time, reversible stationary Markov chain. It can be seen as a special case of Cheeger inequalities in expander graph ...
for
Markov chains
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...
and can be seen as a discrete version of
Cheeger's inequality in
Riemannian geometry
Riemannian geometry is the branch of differential geometry that studies Riemannian manifolds, smooth manifolds with a ''Riemannian metric'', i.e. with an inner product on the tangent space at each point that varies smoothly from point to point ...
.
For general connected graphs that are not necessarily regular, an alternative inequality is given by Chung
:
where
is the least nontrivial eigenvalue of the normalized Laplacian, and
is the (normalized) Cheeger constant
:
where
is the sum of degrees of vertices in
.
Hoffman–Delsarte inequality
There is an eigenvalue bound for
independent sets in
regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegr ...
s, originally due to
Alan J. Hoffman and Philippe Delsarte.
Suppose that
is a
-regular graph on
vertices with least eigenvalue
. Then:
where
denotes its
independence number.
This bound has been applied to establish e.g. algebraic proofs of the
Erdős–Ko–Rado theorem and its analogue for intersecting families of subspaces over
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
s.
For general graphs which are not necessarily regular, a similar upper bound for the independence number can be derived by using the maximum eigenvalue
of the normalized Laplacian
[ of :
where and denote the maximum and minimum degree in , respectively. This a consequence of a more general inequality (pp. 109 in
][):
where is an independent set of vertices and denotes the sum of degrees of vertices in .
]
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.[''Eigenspaces of Graphs'', by Dragoš Cvetković, Peter Rowlinson, Slobodan Simić (1997) ] The 1980 monograph ''Spectra of Graphs'' 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''. The 3rd edition of ''Spectra of Graphs'' (1995) contains a summary of the further recent contributions to the subject.[ Discrete geometric analysis created and developed by ]Toshikazu Sunada
is a Japanese mathematician and author of many books and essays on mathematics and mathematical sciences. He is professor emeritus of both Meiji University and Tohoku University. He is also distinguished professor of emeritus at Meiji in recogni ...
in the 2000s deals with spectral graph theory in terms of discrete Laplacians associated with weighted graphs, and finds application in various fields, including shape analysis. In most recent years, the spectral graph theory has expanded to vertex-varying graphs often encountered in many real-life applications.
See also
* Strongly regular graph
In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that:
* Every two adjacent vertices have comm ...
* Algebraic connectivity
The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue after Miroslav Fiedler) of a graph ''G'' is the second-smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of ''G''. This eigenvalue i ...
* Algebraic graph theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph th ...
* Spectral clustering
In multivariate statistics, spectral clustering techniques make use of the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering in fewer dimensions. The similarity matrix is provided as ...
* Spectral shape analysis Spectral shape analysis relies on the spectrum (eigenvalues and/or eigenfunctions) of the Laplace–Beltrami operator to compare and analyze geometric shapes. Since the spectrum of the Laplace–Beltrami operator is invariant under isometries, it ...
* Estrada index
* Lovász theta
* Expander graph
In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applica ...
References
* .
*
*
*
*
External links
* hapter from Combinatorial Scientific Computing* resented at FOCS 2007 Conference* ourse page and lecture notes
{{DEFAULTSORT:Spectral Graph Theory
*
*