Spectral graph theory

Spectral graph theory is a fun part of mathematics that helps us learn about graphs. Graphs are like maps with points connected by lines. In spectral graph theory, we study how the features of a graph connect to special numbers and patterns called eigenvalues and eigenvectors. These come from matrices, which are square tables of numbers. Two important matrices are the adjacency matrix and the Laplacian matrix.

The adjacency matrix of a simple graph, where lines connect points without directions, is a special number table. It has nice symmetrical properties. This means its eigenvalues — the special numbers we get from the matrix — are always real. We can organize the matrix in a neat way using orthogonal diagonalization.

Even if we change the labels of the points in the graph, the adjacency matrix changes. But the set of its eigenvalues, called the spectrum, stays the same. This makes the spectrum a helpful tool because it doesn’t depend on how we name the points. However, it doesn’t tell us everything about the graph by itself. Spectral graph theory also studies graph features based on how many times certain eigenvalues appear, like the Colin de Verdière number.

Cospectral graphs

Two graphs are called cospectral if their adjacency matrices have the same eigenvalues. This means that even though these graphs might look different, their matrices share the same numerical properties.

Not all cospectral graphs look the same, but graphs that do look the same will always be cospectral.

Cheeger inequality

The Cheeger inequality is an important idea in spectral graph theory. It connects the shape of a graph to numbers called eigenvalues from a special matrix called the Laplacian. This helps us understand how spread out the connections in a graph can be.

The Cheeger constant measures if a graph has a "bottleneck," which is a small cut that separates the graph into two parts. This idea is useful in many areas, like designing computer networks or studying shapes in topology. There are special math rules that relate the Cheeger constant to eigenvalues, showing how tightly connected the graph is.

Hoffman–Delsarte inequality

The Hoffman–Delsarte inequality is a rule that helps us understand how large a special group of points, called an independent set, can be in a type of graph known as a regular graph.

This rule uses numbers from the graph, like the smallest value from a special list of numbers related to the graph, to find an upper limit on the size of these independent sets. It can also be used for graphs that are not regular, using a different set of numbers from the graph.

Historical outline

Spectral graph theory began to grow in the 1950s and 1960s. It started from two places: studies about graphs and work in quantum chemistry. People found these connections later. In 1980, a book called Spectra of Graphs by Cvetković, Doob, and Sachs collected almost all the research done up to that time. The book was updated in 1988 and again in 1995.

Later, a new area called discrete geometric analysis was created by Toshikazu Sunada in the 2000s. This uses special math tools to study graphs. It is used in fields like shape analysis. More recently, vertex-frequency analysis was developed to help solve problems in areas such as signal processing.