Informally, a graph is a good expander if it has low degree and high expansion parameters.
The edge expansion normalizes this concept by dividing with smallest number of vertices among the two parts.
If we want to write h(G) with an optimization over all non-empty subsets, we can rewrite it as The vertex isoperimetric number hout(G) (also vertex expansion or magnification) of a graph G is defined as where ∂out(S) is the outer boundary of S, i.e., the set of vertices in V(G) \ S with at least one neighbor in S.[3] In a variant of this definition (called unique neighbor expansion) ∂out(S) is replaced by the set of vertices in V with exactly one neighbor in S.[4] The vertex isoperimetric number hin(G) of a graph G is defined as where
The bound given by an (n, d, λ)-graph on λi for i ≠ 1 is useful many contexts, including the expander mixing lemma.
with ui = 1⁄n for all i = 1, …, n is the stationary distribution of G. That is, we have Au = du, and u is an eigenvector of A with eigenvalue λ1 = d, where d is the degree of the vertices of G. The spectral gap of G is defined to be d − λ2, and it measures the spectral expansion of the graph G.[7] If we set as this is the largest eigenvalue corresponding to an eigenvector orthogonal to u, it can be equivalently defined using the Rayleigh quotient: where is the 2-norm of the vector
When G is d-regular, meaning each vertex is of degree d, there is a relationship between the isoperimetric constant h(G) and the gap d − λ2 in the spectrum of the adjacency operator of G. By standard spectral graph theory, the trivial eigenvalue of the adjacency operator of a d-regular graph is λ1 = d and the first non-trivial eigenvalue is λ2.
If G is connected, then λ2 < d. An inequality due to Dodziuk[8] and independently Alon and Milman[9] states that[10] In fact, the lower bound is tight.
.By a theorem of Alon and Boppana, all sufficiently large d-regular graphs satisfy
Lubotzky, Phillips, and Sarnak (1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly.
[18] In 1985, Alon, conjectured that most d-regular graphs on n vertices, for sufficiently large n, are almost Ramanujan.
for every ε > 0 with probability 1 – O(n-τ), where[20][21] A simpler proof of a slightly weaker result was given by Puder.
[22][23][24] Marcus, Spielman and Srivastava,[25][26] gave a construction of bipartite Ramanujan graphs based on lifts.
An r-lift of a graph is formed by replacing each vertex by r vertices, and each edge by a matching between the corresponding sets of
They also showed that if the starting graph is a good enough expander, then a good 2-lift can be found in polynomial time, thus giving an efficient construction of d-regular expanders for every d. Bilu and Linial conjectured that the bound
This conjecture was proved in the bipartite setting by Marcus, Spielman and Srivastava,[25][26] who used the method of interlacing polynomials.
[31] There are many results that show the existence of graphs with good expansion properties through probabilistic arguments.
In fact, the existence of expanders was first proved by Pinsker[32] who showed that for a randomly chosen n vertex left d regular bipartite graph, |N(S)| ≥ (d – 2)|S| for all subsets of vertices |S| ≤ cdn with high probability, where cd is a constant depending on d that is O(d-4).
In 2021, Alexander modified an MCMC algorithm to look for randomized constructions to produce Ramanujan graphs with a fixed vertex size and degree of regularity.
[DOI: 10.48550/arXiv.2110.01407] The results show the Ramanujan graphs exist for every vertex size and degree pair up to 2000 vertices.
In 2024 Alon produced an explicit construction for near Ramanujan graphs of every vertex size and degree pair.
The original motivation for expanders is to build economical robust networks (phone or computer): an expander with bounded degree is precisely an asymptotic robust graph with the number of edges growing linearly with size (number of vertices), for all subsets.
Expander graphs have found extensive applications in computer science, in designing algorithms, error correcting codes, extractors, pseudorandom generators, sorting networks (Ajtai, Komlós & Szemerédi (1983)) and robust computer networks.
They have also been used in proofs of many important results in computational complexity theory, such as SL = L (Reingold (2008)) and the PCP theorem (Dinur (2007)).
In a 2006 survey of expander graphs, Hoory, Linial, and Wigderson split the study of expander graphs into four categories: extremal problems, typical behavior, explicit constructions, and algorithms.
The expander mixing lemma states that for an (n, d, λ)-graph, for any two subsets of the vertices S, T ⊆ V, the number of edges between S and T is approximately what you would expect in a random d-regular graph.
A parallel step consists of performing any number of disjoint comparisons and potentially swapping pairs of compared inputs.
Expander graphs play an important role in the AKS sorting network, which achieves depth O(log n).
While this is asymptotically the best known depth for a sorting network, the reliance on expanders makes the constant bound too large for practical use.
Within the AKS sorting network, expander graphs are used to construct bounded depth ε-halvers.
Alexander, C. "On Near Optimal Expander Graphs of Fixed Size", September 2021, DOI: 10.48550/arXiv.2110.01407