A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Expander graphs are sparse graphs with strong connectivity properties: every subset of vertices has a large boundary (many edges leaving the subset). Formally, a d-regular graph is a (d, lambda)-expander if the second-largest eigenvalue of its adjacency matrix has absolute value at most lambda, where a large spectral gap (d - lambda) indicates strong expansion. Random walks on expanders mix rapidly — reaching near-uniform distribution in O(log n) steps — making them powerful pseudorandom objects. Expanders are used for error-correcting codes, derandomization (replacing truly random bits with pseudorandom walks on expanders), communication networks, and the PCP theorem. Explicit constructions (Ramanujan graphs achieving lambda = 2*sqrt(d-1)) exist via number theory and algebraic geometry.
Expander graphs are sparse graphs that behave like complete graphs in terms of connectivity. A d-regular graph on n vertices has only dn/2 edges (sparse), yet if it is a good expander, every subset S of at most n/2 vertices has at least c*d*|S| edges leaving S (for some constant c). This means information, random walks, and messages spread through the graph as rapidly as on a complete graph, despite the sparsity. The formal measure of expansion quality is the spectral gap: the difference between the largest eigenvalue d and the second-largest eigenvalue lambda_2 of the adjacency matrix.
The spectral gap controls three equivalent (up to polynomial factors) properties. The expander mixing lemma says edge distribution is near-uniform: the number of edges between any two sets S, T deviates from the expected d|S||T|/n by at most lambda_2*sqrt(|S||T|). The Cheeger inequality connects the spectral gap to combinatorial edge expansion: the minimum ratio of boundary edges to subset size. Random walk mixing time is O(log n / log(d/lambda_2)) — a walk reaches near-uniform distribution in logarithmically many steps. All three capture the same phenomenon: information spreads rapidly because the graph has no bottlenecks.
The applications of expanders span computer science. In error-correcting codes, expander graphs yield codes with constant rate and linear-time decoding (Sipser-Spielman). In derandomization, random walks on expanders replace independent random samples with correlated but "sufficiently random" ones, reducing the number of random bits from k*log(n) to log(n) + k*log(d). In network design, expanders provide fault-tolerant communication topologies with low degree. In complexity theory, expanders are essential to the PCP theorem (which characterizes NP in terms of probabilistically checkable proofs) and to the proof that undirected connectivity is in logspace (Reingold, 2005).
Explicit construction of optimal expanders — Ramanujan graphs where lambda_2 = 2*sqrt(d-1) — requires deep algebraic machinery. The Lubotzky-Phillips-Sarnak construction uses Cayley graphs of certain linear groups, with the spectral bound following from the Ramanujan conjecture in the theory of automorphic forms. The Marcus-Spielman-Srivastava breakthrough (2015) used the method of interlacing polynomials to prove existence of bipartite Ramanujan graphs for all degrees. Meanwhile, random regular graphs achieve near-Ramanujan spectral gaps with high probability — illustrating the gap between the probabilistic existence of good combinatorial objects and the difficulty of constructing them explicitly.