Expander graph

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

Definitions

Intuitively, an expander graph is a finite, undirected multigraph in which every subset of the vertices that is not "too large" has a "large" boundary. Different formalisations of these notions give rise to different notions of expanders: edge expanders, vertex expanders, and spectral expanders, as defined below. A disconnected graph is not an expander, since the boundary of a connected component is empty. Every connected finite graph is an expander; however, different connected graphs have different expansion parameters. The complete graph has the best expansion property, but it has largest possible degree. Informally, a graph is a good expander if it has low degree and high expansion parameters.

Edge expansion

The edge expansion (also isoperimetric number or Cheeger constant) of a graph on vertices is defined as h(G) = \min_{0 where \partial S := \{ \{ u, v \} \in E(G) \ : \ u \in S, v \notin S \}, which can also be written as with the complement of and E(A,B) = \{ \{ u, v \} \in E(G) \ : \ u \in A , v \in B \} the edges between the subsets of vertices . In the equation, the minimum is over all nonempty sets of at most vertices and is the edge boundary of , i.e., the set of edges with exactly one endpoint in . Intuitively, \min = \min |E({S}, \overline{S})| is the minimum number of edges that need to be cut in order to split the graph in two. The edge expansion normalizes this concept by dividing with smallest number of vertices among the two parts. To see how the normalization can drastically change the value, consider the following example. Take two complete graphs with the same number of vertices and add edges between the two graphs by connecting their vertices one-to-one. The minimum cut will be but the edge expansion will be 1. Notice that in , the optimization can be equivalently done either over or over any non-empty subset, since E(S, \overline{S}) = E(\overline{S}, S) . The same is not true for because of the normalization by . If we want to write with an optimization over all non-empty subsets, we can rewrite it as h(G) = \min_{\emptyset \subsetneq S\subsetneq V(G) } \frac {\min\ , where is the outer boundary of , i.e., the set of vertices in with at least one neighbor in . In a variant of this definition (called unique neighbor expansion) is replaced by the set of vertices in with exactly one neighbor in . The vertex isoperimetric number of a graph is defined as h_{\text{in}}(G) = \min_{0 where \partial_{\text{in}}(S) is the inner boundary of , i.e., the set of vertices in with at least one neighbor in .

Spectral expansion

When is -regular, a linear algebraic definition of expansion is possible based on the eigenvalues of the adjacency matrix of , where is the number of edges between vertices and . Because is symmetric, the spectral theorem implies that has real-valued eigenvalues . It is known that all these eigenvalues are in and more specifically, it is known that if and only if is bipartite. More formally, we refer to an -vertex, -regular graph with \max_{i \neq 1}|\lambda_i| \leq \lambda as an -graph. The bound given by an -graph on for is useful in many contexts, including the expander mixing lemma. Spectral expansion can be two-sided, as above, with \max_{i \neq 1}|\lambda_i| \leq \lambda , or it can be one-sided, with \max_{i \neq 1}\lambda_i \leq \lambda . The latter is a weaker notion that holds also for bipartite graphs and is still useful for many applications, such as the Alon–Chung lemma. Because is regular, the uniform distribution u\in\R^n with for all is the stationary distribution of . That is, we have , and is an eigenvector of with eigenvalue , where is the degree of the vertices of . The spectral gap of is defined to be , and it measures the spectral expansion of the graph . If we set \lambda=\max\ {n}\right| \leq \lambda \sqrt . Many properties of -graphs are corollaries of the expander mixing lemmas, including the following. An independent set of a graph is a subset of vertices with no two vertices adjacent. In an -graph, an independent set has size at most . The chromatic number of a graph , , is the minimum number of colors needed such that adjacent vertices have different colors. Hoffman showed that , while Alon, Krivelevich, and Sudakov showed that if , then \chi(G) \leq O \left( \frac{d}{\log(1+d/\lambda)} \right). The diameter of a graph is the maximum distance between two vertices, where the distance between two vertices is defined to be the shortest path between them. Chung showed that the diameter of an -graph is at most \left\lceil \log \frac{n}{ \log(d/\lambda)} \right\rceil.

Expander walk sampling

The Chernoff bound states that, when sampling many independent samples from a random variable in the range , with high probability the average of our samples is close to the expectation of the random variable. The expander walk sampling lemma, due to and , states that this also holds true when sampling from a walk on an expander graph. This is particularly useful in the theory of derandomization, since sampling according to an expander walk uses many fewer random bits than sampling independently.

See also

Algebraic connectivity Zig-zag product Superstrong approximation Spectral graph theory

Notes

References

Textbooks and surveys

Research articles

. . .

Recent Applications

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378614164 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

7 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.