随机算法 (Fall 2011)/Expander Graphs
According to wikipedia:
- "Expander graphs have found extensive applications in computer science, in designing algorithms, error correcting codes, extractors, pseudorandom generators, sorting networks and robust computer networks. They have also been used in proofs of many important results in computational complexity theory, such as SL=L and the PCP theorem. In cryptography too, expander graphs are used to construct hash functions."
We will not explore everything about expander graphs, but will focus on the performances of random walks on expander graphs.
Expander graphs
Consider an undirected (multi-)graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G(V,E)} , where the parallel edges between two vertices are allowed.
Some notations:
- For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S,T\subset V} , let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle E(S,T)=\{uv\in E\mid u\in S,v\in T\}} .
- The Edge Boundary of a set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\subset V} , denoted Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \partial S\,} , is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \partial S = E(S, \bar{S})} .
Definition (Graph expansion) - The expansion ratio of an undirected graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G}
on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n}
vertices, is defined as
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \phi(G)=\min_{\overset{S\subset V}{|S|\le\frac{n}{2}}} \frac{|\partial S|}{|S|}. }
- The expansion ratio of an undirected graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G}
on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n}
vertices, is defined as
Expander graphs are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle d} -regular (multi)graphs with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle d=O(1)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \phi(G)=\Omega(1)} .
This definition states the following properties of expander graphs:
- Expander graphs are sparse graphs. This is because the number of edges is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle dn/2=O(n)} .
- Despite the sparsity, expander graphs have good connectivity. This is supported by the expansion ratio.
- This one is implicit: expander graph is a family of graphs Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{G_n\}} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} is the number of vertices. The asymptotic order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle O(1)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega(1)} in the definition is relative to the number of vertices Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} , which grows to infinity.
The following fact is directly implied by the definition.
- An expander graph has diameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle O(\log n)} .
The proof is left for an exercise.
For a vertex set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} , the size of the edge boundary Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\partial S|} can be seen as the "perimeter" of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S|} can be seen as the "volume" of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} . The expansion property can be interpreted as a combinatorial version of isoperimetric inequality.
- Vertex expansion
- We can alternatively define the vertex expansion. For a vertex set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\subset V}
, its vertex boundary, denoted Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \delta S\,}
is defined as that
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \delta S=\{u\not\in S\mid uv\in E \mbox{ and }v\in S\}} ,
- and the vertex expansion of a graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \psi(G)=\min_{\overset{S\subset V}{|S|\le\frac{n}{2}}} \frac{|\delta S|}{|S|}} .
Existence of expander graph
We will show the existence of expander graphs by the probabilistic method. In order to do so, we need to generate random Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle d} -regular graphs.
Suppose that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle d} is even. We can generate a random Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle d} -regular graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G(V,E)} as follows:
- Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle V} be the vertex set. Uniformly and independently choose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \frac{d}{2}} cycles of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle V} .
- For each vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle v} , for every cycle, assuming that the two neighbors of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle v} in that cycle is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle w} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle u} , add two edges Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle wv} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle uv} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle E} .
The resulting Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G(V,E)} is a multigraph. That is, it may have multiple edges between two vertices. We will show that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G(V,E)} is an expander graph with high probability. Formally, for some constant Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle d} and constant Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \alpha} ,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[\phi(G)\ge \alpha]=1-o(1)} .
By the probabilistic method, this shows that there exist expander graphs. In fact, the above probability bound shows something much stronger: it shows that almost every regular graph is an expander.
Recall that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \phi(G)=\min_{S:|S|\le\frac{n}{2}}\frac{|\partial S|}{|S|}} . We call such Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\subset V} that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \frac{|\partial S|}{|S|}<\alpha} a "bad Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} ". Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \phi(G)< \alpha} if and only if there exists a bad Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} of size at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \frac{n}{2}} . Therefore,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \Pr[\phi(G)< \alpha] &= \Pr\left[\min_{S:|S|\le\frac{n}{2}}\frac{|\partial S|}{|S|}<\alpha\right]\\ &= \sum_{k=1}^\frac{n}{2}\Pr[\,\exists \mbox{bad }S\mbox{ of size }k\,]\\ &\le \sum_{k=1}^\frac{n}{2}\sum_{S\in{V\choose k}}\Pr[\,S\mbox{ is bad}\,] \end{align} }
Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R\subset S} be the set of vertices in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} which has neighbors in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \bar{S}} , and let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r=|R|} . It is obvious that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\partial S|\ge r} , thus, for a bad Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r<\alpha k} . Therefore, there are at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \sum_{r=1}^{\alpha k}{k \choose r}} possible choices such Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} . For any fixed choice of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} , the probability that an edge picked by a vertex in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S-R} connects to a vertex in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} is at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k/n} , and there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle d(k-r)} such edges. For any fixed Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r} , the probability that all neighbors of all vertices in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S-R} are in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} is at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \left(\frac{k}{n}\right)^{d(k-r)}} . Due to the union bound, for any fixed Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} ,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \Pr[\,S\mbox{ is bad}\,] &\le \sum_{r=1}^{\alpha k}{k \choose r}\left(\frac{k}{n}\right)^{d(k-r)} \le \alpha k {k \choose \alpha k}\left(\frac{k}{n}\right)^{dk(1-\alpha)} \end{align} }
Therefore,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \Pr[\phi(G)< \alpha] &\le \sum_{k=1}^\frac{n}{2}\sum_{S\in{V\choose k}}\Pr[\,S\mbox{ is bad}\,]\\ &\le \sum_{k=1}^\frac{n}{2}{n\choose k}\alpha k {k \choose \alpha k}\left(\frac{k}{n}\right)^{dk(1-\alpha)} \\ &\le \sum_{k=1}^\frac{n}{2}\left(\frac{en}{k}\right)^k\alpha k \left(\frac{ek}{\alpha k}\right)^{\alpha k}\left(\frac{k}{n}\right)^{dk(1-\alpha)}&\quad (\mbox{Stirling formula }{n\choose k}\le\left(\frac{en}{k}\right)^k)\\ &\le \sum_{k=1}^\frac{n}{2}\exp(O(k))\left(\frac{k}{n}\right)^{k(d(1-\alpha)-1)}. \end{align} }
The last line is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle o(1)} when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle d\ge\frac{2}{1-\alpha}} . Therefore, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G} is an expander graph with expansion ratio Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \alpha} with high probability for suitable choices of constant Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle d} and constant Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \alpha} .
Computing Graph Expansion
Computation of graph expansion seems hard, because the definition involves the minimum over exponentially many subsets of vertices. In fact, the problem of deciding whether a graph is an expander is co-NP-complete. For a non-expander Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G} , the vertex set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\subset V} which has low expansion ratio is a proof of the fact that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle G} is not an expander, which can be verified in poly-time. However, there is no efficient algorithm for computing the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \phi(G)} unless NP=P.
The expansion ratio of a graph is closely related to the sparsest cut of the graph, which is the dual problem of the multicommodity flow problem, both NP-complete. Studies of these two problems revolutionized the area of approximation algorithms.
We will see right now that although it is hard to compute the expansion ratio exactly, the expansion ratio can be approximated by some efficiently computable algebraic identity of the graph.