Expander graph

Template:Short description

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.<ref name="Hoory 2006">Template:Harvtxt</ref>

DefinitionsEdit

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 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 expansionEdit

The edge expansion (also isoperimetric number or Cheeger constant) Template:Math of a graph Template:Mvar on Template:Mvar vertices is defined as

where <math>\partial S := \{ \{ u, v \} \in E(G) \ : \ u \in S, v \notin S \},</math>

which can also be written as Template:Math with Template:Math the complement of Template:Mvar and

the edges between the subsets of vertices Template:Math.

In the equation, the minimum is over all nonempty sets Template:Mvar of at most Template:Math vertices and Template:Math is the edge boundary of Template:Mvar, i.e., the set of edges with exactly one endpoint in Template:Mvar.<ref>Definition 2.1 in Template:Harvtxt</ref>

Intuitively,

<math>\min {|\partial S|} = \min E({S}, \overline{S})</math>

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 Template:Mvar and add Template:Mvar edges between the two graphs by connecting their vertices one-to-one. The minimum cut will be Template:Mvar but the edge expansion will be 1.

Notice that in Template:Math, the optimization can be equivalently done either over Template:Math or over any non-empty subset, since <math>E(S, \overline{S}) = E(\overline{S}, S)</math>. The same is not true for Template:Math because of the normalization by Template:Math. If we want to write Template:Math with an optimization over all non-empty subsets, we can rewrite it as

<math>h(G) = \min_{\emptyset \subsetneq S\subsetneq V(G) } \frac{E({S}, \overline{S})}{\min\{|S|, |\overline{S}|\}}.</math>

Vertex expansionEdit

File:Vertex expansion.svg

</math>, and therefore 0.5 is the vertex expansion of Template:Mvar.

The vertex isoperimetric number Template:Math (also vertex expansion or magnification) of a graph Template:Mvar is defined as

where Template:Math is the outer boundary of Template:Mvar, i.e., the set of vertices in Template:Math with at least one neighbor in Template:Mvar.<ref name="BobkovHoudre">Template:Harvtxt</ref> In a variant of this definition (called unique neighbor expansion) Template:Math is replaced by the set of vertices in Template:Mvar with exactly one neighbor in Template:Mvar.<ref name="AlonCapalbo">Template:Harvtxt</ref>

The vertex isoperimetric number Template:Math of a graph Template:Mvar is defined as

where <math>\partial_{\text{in}}(S)</math> is the inner boundary of Template:Mvar, i.e., the set of vertices in Template:Mvar with at least one neighbor in Template:Math.<ref name="BobkovHoudre" />

Spectral expansionEdit

When Template:Mvar is [[regular graph|Template:Mvar-regular]], a linear algebraic definition of expansion is possible based on the eigenvalues of the adjacency matrix Template:Math of Template:Mvar, where Template:Mvar is the number of edges between vertices Template:Mvar and Template:Mvar.<ref>cf. Section 2.3 in Template:Harvtxt</ref> Because Template:Mvar is symmetric, the spectral theorem implies that Template:Mvar has Template:Mvar real-valued eigenvalues Template:Math. It is known that all these eigenvalues are in Template:Math and more specifically, it is known that Template:Math if and only if Template:Mvar is bipartite.

More formally, we refer to an Template:Mvar-vertex, Template:Mvar-regular graph with

<math>\max_{i \neq 1}|\lambda_i| \leq \lambda</math>

as an Template:Math-graph. The bound given by an Template:Math-graph on Template:Math for Template:Math is useful in many contexts, including the expander mixing lemma.

Spectral expansion can be two-sided, as above, with <math>\max_{i \neq 1}|\lambda_i| \leq \lambda</math>, or it can be one-sided, with <math>\max_{i \neq 1}\lambda_i \leq \lambda</math>. 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.<ref>N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks. Discrete Math., vol. 72, pp. 15–19, 1988.</ref>

Because Template:Mvar is regular, the uniform distribution <math>u\in\R^n</math> with Template:Math for all Template:Math is the stationary distribution of Template:Mvar. That is, we have Template:Math, and Template:Mvar is an eigenvector of Template:Mvar with eigenvalue Template:Math, where Template:Mvar is the degree of the vertices of Template:Mvar. The spectral gap of Template:Mvar is defined to be Template:Math, and it measures the spectral expansion of the graph Template:Mvar.<ref>This definition of the spectral gap is from Section 2.3 in Template:Harvtxt</ref>

If we set

<math>\lambda=\max\{|\lambda_2|, |\lambda_n|\}</math>

as this is the largest eigenvalue corresponding to an eigenvector orthogonal to Template:Mvar, it can be equivalently defined using the Rayleigh quotient:

<math>\lambda=\max_{v \perp u , v \neq 0} \frac{\|Av\|_2}{\|v\|_2},</math>

where

<math>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1/2}</math>

is the 2-norm of the vector <math>v\in\R^n</math>.

The normalized versions of these definitions are also widely used and more convenient in stating some results. Here one considers the matrix Template:Math, which is the Markov transition matrix of the graph Template:Mvar. Its eigenvalues are between −1 and 1. For not necessarily regular graphs, the spectrum of a graph can be defined similarly using the eigenvalues of the Laplacian matrix. For directed graphs, one considers the singular values of the adjacency matrix Template:Mvar, which are equal to the roots of the eigenvalues of the symmetric matrix Template:Math.

Relationships between different expansion propertiesEdit

The expansion parameters defined above are related to each other. In particular, for any Template:Mvar-regular graph Template:Mvar,

Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.

Cheeger inequalitiesEdit

When Template:Mvar is Template:Mvar-regular, meaning each vertex is of degree Template:Mvar, there is a relationship between the isoperimetric constant Template:Math and the gap Template:Math in the spectrum of the adjacency operator of Template:Mvar. By standard spectral graph theory, the trivial eigenvalue of the adjacency operator of a Template:Mvar-regular graph is Template:Math and the first non-trivial eigenvalue is Template:Math. If Template:Mvar is connected, then Template:Math. An inequality due to DodziukTemplate:Sfn and independently Alon and Milman Template:Sfn states that<ref>Theorem 2.4 in Template:Harvtxt</ref>

<math>\tfrac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}.</math>

In fact, the lower bound is tight. The lower bound is achieved in limit for the hypercube Template:Mvar, where Template:Math and Template:Math. The upper bound is (asymptotically) achieved for a cycle, where Template:Math and Template:Math.<ref name="Hoory 2006"/> A better bound is given in <ref>B. Mohar. Isoperimetric numbers of graphs. J. Combin. Theory Ser. B, 47(3):274–291, 1989.</ref> as

<math> h(G) \le \sqrt{d^2 - \lambda_2^2}.</math>

These inequalities are closely related to the Cheeger bound for Markov chains and can be seen as a discrete version of Cheeger's inequality in Riemannian geometry.

Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:<ref>See Theorem 1 and p.156, l.1 in Template:Harvtxt. Note that Template:Math there corresponds to Template:Math of the current article (see p.153, l.5)</ref>

<math>h_{\text{out}}(G)\le \left(\sqrt{4 (d-\lambda_2)} + 1\right)^2 -1</math>

<math>h_{\text{in}}(G) \le \sqrt{8(d-\lambda_2)}.</math>

Asymptotically speaking, the quantities Template:Math, Template:Math, and Template:Math are all bounded above by the spectral gap Template:Math.

ConstructionsEdit

There are four general strategies for explicitly constructing families of expander graphs.<ref>see, e.g., Template:Harvtxt</ref> The first strategy is algebraic and group-theoretic, the second strategy is analytic and uses additive combinatorics, the third strategy is combinatorial and uses the zig-zag and related graph products, and the fourth strategy is based on lifts. Noga Alon showed that certain graphs constructed from finite geometries are the sparsest examples of highly expanding graphs.<ref>Template:Cite journal</ref>

Margulis–Gabber–GalilEdit

Algebraic constructions based on Cayley graphs are known for various variants of expander graphs. The following construction is due to Margulis and has been analysed by Gabber and Galil.<ref>see, e.g., p.9 of Template:Harvtxt</ref> For every natural number Template:Mvar, one considers the graph Template:Mvar with the vertex set <math>\mathbb Z_n \times \mathbb Z_n</math>, where <math>\mathbb Z_n=\mathbb Z/n\mathbb Z</math>: For every vertex <math>(x,y)\in\mathbb Z_n \times \mathbb Z_n</math>, its eight adjacent vertices are

Then the following holds:

Theorem. For all Template:Mvar, the graph Template:Mvar has second-largest eigenvalue <math>\lambda(G)\leq 5 \sqrt{2}</math>.

Ramanujan graphsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} By a theorem of Alon and Boppana, all sufficiently large Template:Mvar-regular graphs satisfy <math>\lambda_2 \ge 2\sqrt{d-1} - o(1)</math>, where Template:Math is the second largest eigenvalue in absolute value.<ref>Theorem 2.7 of Template:Harvtxt</ref> As a direct consequence, we know that for every fixed Template:Mvar and <math>\lambda< 2 \sqrt{d-1}</math> , there are only finitely many Template:Math-graphs. Ramanujan graphs are Template:Mvar-regular graphs for which this bound is tight, satisfying <ref>Definition 5.11 of Template:Harvtxt</ref>

<math>\lambda = \max_{|\lambda_i| < d} |\lambda_i| \le 2\sqrt{d-1}.</math>

Hence Ramanujan graphs have an asymptotically smallest possible value of Template:Math. This makes them excellent spectral expanders.

Lubotzky, Phillips, and Sarnak (1988), Margulis (1988), and Morgenstern (1994) show how Ramanujan graphs can be constructed explicitly.<ref>Theorem 5.12 of Template:Harvtxt</ref>

In 1985, Alon, conjectured that most Template:Mvar-regular graphs on Template:Mvar vertices, for sufficiently large Template:Mvar, are almost Ramanujan.<ref>Template:Cite journal</ref> That is, for Template:Math, they satisfy

<math>\lambda \le 2\sqrt{d-1}+\varepsilon</math>.

In 2003, Joel Friedman both proved the conjecture and specified what is meant by "most Template:Mvar-regular graphs" by showing that [[Random regular graph|random Template:Mvar-regular graphs]] have <math>\lambda \le 2\sqrt{d-1}+\varepsilon</math> for every Template:Math with probability Template:Math, where<ref>Template:Cite arXiv</ref><ref>Theorem 7.10 of Template:Harvtxt</ref>

<math>\tau = \left\lceil\frac{\sqrt{d-1} +1}{2} \right\rceil.</math>

A simpler proof of a slightly weaker result was given by Puder.<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref><ref>Template:Cite journal</ref>

Marcus, Spielman and Srivastava,<ref name="mss13">Template:Cite conference</ref><ref name="mss15">Template:Cite conference</ref> gave a construction of bipartite Ramanujan graphs based on lifts.

In 2024 a preprint by Jiaoyang Huang, Theo McKenzieand and Horng-Tzer Yau proved that

<math>\lambda \le 2\sqrt{d-1}</math>.

with the fraction of eigenvalues that hit the Alon-Boppana bound approximately 69% from proving that edge universality holds, that is they follow a Tracy-Widom distribution associated with the Gaussian Orthogonal Ensemble<ref>Template:Cite arXiv</ref><ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

Zig-zag productEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Reingold, Vadhan, and Wigderson introduced the zig-zag product in 2003.<ref name=":0">Template:Cite book</ref> Roughly speaking, the zig-zag product of two expander graphs produces a graph with only slightly worse expansion. Therefore, a zig-zag product can also be used to construct families of expander graphs. If Template:Mvar is a Template:Math-graph and Template:Mvar is an Template:Math-graph, then the zig-zag product Template:Math is a Template:Math-graph where Template:Mvar has the following properties.

If Template:Math and Template:Math, then Template:Math;
Template:Math.

Specifically,<ref name=":0" />

<math>\phi(\lambda_1, \lambda_2)=\frac{1}{2}(1-\lambda^2_2)\lambda_2 +\frac{1}{2}\sqrt{(1-\lambda^2_2)^2\lambda_1^2 +4\lambda^2_2}.</math>

Note that property (1) implies that the zig-zag product of two expander graphs is also an expander graph, thus zig-zag products can be used inductively to create a family of expander graphs.

Intuitively, the construction of the zig-zag product can be thought of in the following way. Each vertex of Template:Mvar is blown up to a "cloud" of Template:Mvar vertices, each associated to a different edge connected to the vertex. Each vertex is now labeled as Template:Math where Template:Mvar refers to an original vertex of Template:Mvar and Template:Mvar refers to the Template:Mvarth edge of Template:Mvar. Two vertices, Template:Math and Template:Math are connected if it is possible to get from Template:Math to Template:Math through the following sequence of moves.

Zig – Move from Template:Math to Template:Math, using an edge of Template:Mvar.
Jump across clouds using edge Template:Mvar in Template:Mvar to get to Template:Math.
Zag – Move from Template:Math to Template:Math using an edge of Template:Mvar.<ref name=":0" />

LiftsEdit

An [[Covering graph|Template:Mvar-lift]] of a graph is formed by replacing each vertex by Template:Mvar vertices, and each edge by a matching between the corresponding sets of <math>r</math> vertices. The lifted graph inherits the eigenvalues of the original graph, and has some additional eigenvalues. Bilu and Linial<ref>Template:Cite arXiv</ref><ref>Template:Cite journal</ref> showed that every Template:Mvar-regular graph has a 2-lift in which the additional eigenvalues are at most <math>O(\sqrt{d\log^3 d})</math> in magnitude. 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 Template:Mvar-regular expanders for every Template:Mvar.

Bilu and Linial conjectured that the bound <math>O(\sqrt{d\log^3 d})</math> can be improved to <math>2\sqrt{d-1}</math>, which would be optimal due to the Alon–Boppana bound. This conjecture was proved in the bipartite setting by Marcus, Spielman and Srivastava,<ref name="mss13"/><ref name="mss15"/> who used the method of interlacing polynomials. As a result, they obtained an alternative construction of bipartite Ramanujan graphs. The original non-constructive proof was turned into an algorithm by Michael B. Cohen.<ref name="c16">Template:Cite conference</ref> Later the method was generalized to Template:Mvar-lifts by Hall, Puder and Sawin.<ref>Template:Cite journal</ref>

Randomized constructionsEdit

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<ref>Template:Cite journal</ref> who showed that for a randomly chosen Template:Mvar vertex left Template:Mvar regular bipartite graph, Template:Math for all subsets of vertices Template:Math with high probability, where Template:Mvar is a constant depending on Template:Mvar that is Template:Math. Alon and Roichman <ref>Template:Cite journal</ref> showed that for every Template:Math, there is some Template:Math such that the following holds: For a group Template:Mvar of order Template:Mvar, consider the Cayley graph on Template:Mvar with Template:Math randomly chosen elements from Template:Mvar. Then, in the limit of Template:Mvar getting to infinity, the resulting graph is almost surely an Template:Math-expander.

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.<ref>Template:Cite arXiv</ref> 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.

Applications and useful propertiesEdit

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 (Template:Harvtxt) and robust computer networks. They have also been used in proofs of many important results in computational complexity theory, such as SL = L (Template:Harvtxt) and the PCP theorem (Template:Harvtxt). In cryptography, expander graphs are used to construct hash functions.

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. Extremal problems focus on the bounding of expansion parameters, while typical behavior problems characterize how the expansion parameters are distributed over random graphs. Explicit constructions focus on constructing graphs that optimize certain parameters, and algorithmic questions study the evaluation and estimation of parameters.

Expander mixing lemmaEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} The expander mixing lemma states that for an Template:Math-graph, for any two subsets of the vertices Template:Math, the number of edges between Template:Mvar and Template:Mvar is approximately what you would expect in a random Template:Mvar-regular graph. The approximation is better the smaller Template:Math is. In a random Template:Mvar-regular graph, as well as in an Erdős–Rényi random graph with edge probability Template:Math, we expect Template:Math edges between Template:Mvar and Template:Mvar.

More formally, let Template:Math denote the number of edges between Template:Mvar and Template:Mvar. If the two sets are not disjoint, edges in their intersection are counted twice, that is,

<math>E(S,T)=2|E(G[S\cap T])| + E(S\setminus T,T) + E(S,T\setminus S). </math>

Then the expander mixing lemma says that the following inequality holds:

<math>\left|E(S, T) - \frac{d \cdot |S| \cdot |T|}{n}\right| \leq \lambda \sqrt{|S| \cdot |T|}.</math>

Many properties of Template:Math-graphs are corollaries of the expander mixing lemmas, including the following.<ref name="Hoory 2006"/>

An independent set of a graph is a subset of vertices with no two vertices adjacent. In an Template:Math-graph, an independent set has size at most Template:Math.
The chromatic number of a graph Template:Mvar, Template:Math, is the minimum number of colors needed such that adjacent vertices have different colors. Hoffman showed that Template:Math,<ref>Template:Cite journal</ref> while Alon, Krivelevich, and Sudakov showed that if Template:Math, then<ref>Template:Cite journal</ref>

<math>\chi(G) \leq O \left( \frac{d}{\log(1+d/\lambda)} \right).</math>

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 Template:Math-graph is at most<ref>Template:Cite journal</ref>

<math>\left\lceil \log \frac{n}{ \log(d/\lambda)} \right\rceil.</math>

Expander walk samplingEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} The Chernoff bound states that, when sampling many independent samples from a random variable in the range Template:Math, with high probability the average of our samples is close to the expectation of the random variable. The expander walk sampling lemma, due to Template:Harvtxt and Template:Harvtxt, 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.

AKS sorting network and approximate halversEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

Sorting networks take a set of inputs and perform a series of parallel steps to sort the inputs. A parallel step consists of performing any number of disjoint comparisons and potentially swapping pairs of compared inputs. The depth of a network is given by the number of parallel steps it takes. Expander graphs play an important role in the AKS sorting network, which achieves depth Template:Math. 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 Template:Mvar-halvers. An Template:Mvar-halver takes as input a length Template:Mvar permutation of Template:Math and halves the inputs into two disjoint sets Template:Mvar and Template:Mvar such that for each integer Template:Math at most Template:Mvar of the Template:Mvar smallest inputs are in Template:Mvar and at most Template:Mvar of the Template:Mvar largest inputs are in Template:Mvar. The sets Template:Mvar and Template:Mvar are an Template:Mvar-halving.

Following Template:Harvtxt, a depth Template:Mvar Template:Mvar-halver can be constructed as follows. Take an Template:Mvar vertex, degree Template:Mvar bipartite expander with parts Template:Mvar and Template:Mvar of equal size such that every subset of vertices of size at most Template:Mvar has at least Template:Math neighbors.

The vertices of the graph can be thought of as registers that contain inputs and the edges can be thought of as wires that compare the inputs of two registers. At the start, arbitrarily place half of the inputs in Template:Mvar and half of the inputs in Template:Mvar and decompose the edges into Template:Mvar perfect matchings. The goal is to end with Template:Mvar roughly containing the smaller half of the inputs and Template:Mvar containing roughly the larger half of the inputs. To achieve this, sequentially process each matching by comparing the registers paired up by the edges of this matching and correct any inputs that are out of order. Specifically, for each edge of the matching, if the larger input is in the register in Template:Mvar and the smaller input is in the register in Template:Mvar, then swap the two inputs so that the smaller one is in Template:Mvar and the larger one is in Template:Mvar. It is clear that this process consists of Template:Mvar parallel steps.

After all Template:Mvar rounds, take Template:Mvar to be the set of inputs in registers in Template:Mvar and Template:Mvar to be the set of inputs in registers in Template:Mvar to obtain an Template:Mvar-halving. To see this, notice that if a register Template:Mvar in Template:Mvar and Template:Mvar in Template:Mvar are connected by an edge Template:Mvar then after the matching with this edge is processed, the input in Template:Mvar is less than that of Template:Mvar. Furthermore, this property remains true throughout the rest of the process. Now, suppose for some Template:Math that more than Template:Mvar of the inputs Template:Math are in Template:Mvar. Then by expansion properties of the graph, the registers of these inputs in Template:Mvar are connected with at least Template:Math registers in Template:Mvar. Altogether, this constitutes more than Template:Mvar registers so there must be some register Template:Mvar in Template:Mvar connected to some register Template:Mvar in Template:Mvar such that the final input of Template:Mvar is not in Template:Math, while the final input of Template:Mvar is. This violates the previous property however, and thus the output sets Template:Mvar and Template:Mvar must be an Template:Mvar-halving.

NotesEdit

Template:Reflist

Template:Cite arXiv

ReferencesEdit

Template:Refbegin

Textbooks and surveysEdit

Research articlesEdit

Recent ApplicationsEdit

Template:Citation

Template:Refend