Expanders

Expanders are a class of graphs that are simultaneously sparse and highly connected. In many formulations, an expander family is a sequence of graphs with bounded degree that remain well connected as the number of vertices grows. This combination makes expanders useful in both theory and applications.

A common way to measure expansion is via edge expansion. For a d-regular graph G = (V,E), the edge expansion h(G) is defined as the minimum, over all nonempty subsets S of V with size at most |V|/2, of the ratio |∂S|/|S|, where ∂S denotes the set of edges leaving S. A family of graphs is called an expander family if there exists ε > 0 such that h(G) ≥ ε for every graph G in the family (with n = |V| growing). Another perspective uses spectral expansion: the second largest eigenvalue (in absolute value) λ2 of the adjacency matrix or the normalized Laplacian controls expansion; a larger spectral gap (difference between the top eigenvalue and λ2) implies stronger expansion. By Cheeger-type inequalities, expansion and spectral gap are closely linked.

Expanders can be random or explicit. Random d-regular graphs with fixed d ≥ 3 are expanders with high probability. Explicit constructions include Margulis graphs and the Lubotzky–Phillips–Sarnak (LPS) Ramanujan graphs, among others. Ramanujan graphs achieve near-optimal spectral gaps for their degree, making them particularly strong expanders.

Applications span computer science and mathematics. They are used in robust network design, error-correcting codes, derandomization and pseudorandomness, fast mixing of random walks, communication and data structures, and property testing. Expanders also serve as a fundamental tool in complexity theory and combinatorics.