Spectral graph theory

Spectral graph theory is a fascinating area of mathematics that helps us understand graphs — which are like maps of points connected by lines — by using numbers and equations. In mathematics, spectral graph theory studies how the properties of a graph relate to special numbers and patterns called eigenvalues and eigenvectors. These come from matrices, which are square tables of numbers, linked to the graph, such as the adjacency matrix or the Laplacian matrix.

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

Even though changing the labels of the points in the graph changes the adjacency matrix itself, the set of its eigenvalues, called the spectrum, remains the same. This makes the spectrum a useful tool because it doesn’t depend on how we name the points, though it doesn’t tell us everything about the graph on its own. Spectral graph theory also looks at graph features defined by how many times certain eigenvalues appear, such as 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. For example, the smallest pair of cospectral graphs that are not the same shape was discovered in 1957.

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 "sparse" or 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 big 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 started to grow in the 1950s and 1960s. It came from two places: studies about graphs and work in quantum chemistry. These connections were only found much 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 and is used in fields like shape analysis. More recently, vertex-frequency analysis was developed to help solve problems in areas such as signal processing.