imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| =Expander Graphs= | | ==Problem 1 == |
| According to wikipedia:
| | An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be transitive, if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>. |
| :"[http://en.wikipedia.org/wiki/Expander_graph Expander graphs] have found extensive applications in computer science, in designing algorithms, [http://en.wikipedia.org/wiki/Error_correcting_code error correcting codes], [http://en.wikipedia.org/wiki/Extractor_(mathematics) extractors], [http://en.wikipedia.org/wiki/Pseudorandom_generator pseudorandom generators], [http://en.wikipedia.org/wiki/Sorting_network sorting networks] and robust computer networks. They have also been used in proofs of many important results in computational complexity theory, such as [http://en.wikipedia.org/wiki/SL_(complexity) SL]=[http://en.wikipedia.org/wiki/L_(complexity) L] and the [http://en.wikipedia.org/wiki/PCP_theorem PCP theorem]. In [http://en.wikipedia.org/wiki/Cryptography 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.
| | Show that for any <math>k\ge 3</math>, there exists an <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players. |
|
| |
|
| Consider an undirected (multi-)graph <math>G(V,E)</math>, where the parallel edges between two vertices are allowed.
| | == Problem 2 == |
| | Let <math>G(U,V,E)</math> be a bipartite graph. Let <math>\delta_U</math> be the '''minimum''' degree of vertices in <math>U</math>, and <math>\Delta_V</math> be the maximum degree of vertices in <math>V</math>. |
|
| |
|
| Some notations:
| | Show that if <math>\delta_U\ge \Delta_V</math>, then there must be a matching in <math>G</math> such that all vertices in <math>U</math> are matched. |
| * For <math>S,T\subset V</math>, let <math>E(S,T)=\{uv\in E\mid u\in S,v\in T\}</math>.
| |
| * The '''Edge Boundary''' of a set <math>S\subset V</math>, denoted <math>\partial S\,</math>, is <math>\partial S = E(S, \bar{S})</math>.
| |
|
| |
|
| {{Theorem
| | == Problem 3 == |
| |Definition (Graph expansion)|
| | Prove the following statement: |
| :The '''expansion ratio''' of an undirected graph <math>G</math> on <math>n</math> vertices, is defined as
| | * For any <math>n</math> distinct finite sets <math>S_1,S_2,\ldots,S_n</math>, there always is a collection <math>\mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\}</math> such that <math>|\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor</math> and for any different <math>A,B,C\in\mathcal{F}</math> we have <math>A\cup B\neq C</math>. |
| ::<math>
| |
| \phi(G)=\min_{\overset{S\subset V}{|S|\le\frac{n}{2}}} \frac{|\partial S|}{|S|}. | |
| </math> | |
| }}
| |
|
| |
|
| '''Expander graphs''' are '''<math>d</math>-regular''' (multi)graphs with <math>d=O(1)</math> and <math>\phi(G)=\Omega(1)</math>.
| | (Hint: use Dilworth theorem.) |
|
| |
|
| This definition states the following properties of expander graphs:
| | == Problem 4== |
| * Expander graphs are sparse graphs. This is because the number of edges is <math>dn/2=O(n)</math>.
| | A Boolean matrix is a matrix whose entries are either 0 or 1. We call a matrix '''1-matrix''' if all its entries are 1. |
| * 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'' <math>\{G_n\}</math>, where <math>n</math> is the number of vertices. The asymptotic order <math>O(1)</math> and <math>\Omega(1)</math> in the definition is relative to the number of vertices <math>n</math>, which grows to infinity.
| | Let <math>A</math> be a Boolean matrix satisfying: |
| | | * there are totally <math>m</math> 1-entries in <math>A</math>; |
| The following fact is directly implied by the definition.
| | * every row of <math>A</math> contains at most <math>s</math> 1-entries; |
| :;An expander graph has diameter <math>O(\log n)</math>.
| | * <math>A</math> does not contain any <math>r\times r</math> 1-matrix as submatrix. |
| The proof is left for an exercise.
| | Use König-Egerváry Theorem to prove: we need at least <math>\frac{m}{sr}</math> many 1-matrices to precisely cover all the 1s in <math>A</math>. |
| | |
| For a vertex set <math>S</math>, the size of the edge boundary <math>|\partial S|</math> can be seen as the "perimeter" of <math>S</math>, and <math>|S|</math> can be seen as the "volume" of <math>S</math>. The expansion property can be interpreted as a combinatorial version of [http://en.wikipedia.org/wiki/Isoperimetric_inequality isoperimetric inequality].
| |
| | |
| ;Vertex expansion
| |
| :We can alternatively define the '''vertex expansion'''. For a vertex set <math>S\subset V</math>, its '''vertex boundary''', denoted <math>\delta S\,</math> is defined as that
| |
| :: <math>\delta S=\{u\not\in S\mid uv\in E \mbox{ and }v\in S\}</math>,
| |
| :and the '''vertex expansion''' of a graph <math>G</math> is <math>\psi(G)=\min_{\overset{S\subset V}{|S|\le\frac{n}{2}}} \frac{|\delta S|}{|S|}</math>.
| |
| | |
| == 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 <math>d</math>-regular graphs.
| |
| | |
| Suppose that <math>d</math> is even. We can generate a random <math>d</math>-regular graph <math>G(V,E)</math> as follows:
| |
| * Let <math>V</math> be the vertex set. Uniformly and independently choose <math>\frac{d}{2}</math> cycles of <math>V</math>.
| |
| * For each vertex <math>v</math>, for every cycle, assuming that the two neighbors of <math>v</math> in that cycle is <math>w</math> and <math>u</math>, add two edges <math>wv</math> and <math>uv</math> to <math>E</math>.
| |
| | |
| The resulting <math>G(V,E)</math> is a multigraph. That is, it may have multiple edges between two vertices. We will show that <math>G(V,E)</math> is an expander graph with high probability. Formally, for some constant <math>d</math> and constant <math>\alpha</math>,
| |
| :<math>\Pr[\phi(G)\ge \alpha]=1-o(1)</math>.
| |
| | |
| 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 <math>\phi(G)=\min_{S:|S|\le\frac{n}{2}}\frac{|\partial S|}{|S|}</math>. We call such <math>S\subset V</math> that <math>\frac{|\partial S|}{|S|}<\alpha</math> a "bad <math>S</math>". Then <math>\phi(G)< \alpha</math> if and only if there exists a bad <math>S</math> of size at most <math>\frac{n}{2}</math>. Therefore,
| |
| :<math>
| |
| \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}
| |
| </math>
| |
| Let <math>R\subset S</math> be the set of vertices in <math>S</math> which has neighbors in <math>\bar{S}</math>, and let <math>r=|R|</math>. It is obvious that <math>|\partial S|\ge r</math>, thus, for a bad <math>S</math>, <math>r<\alpha k</math>. Therefore, there are at most <math>\sum_{r=1}^{\alpha k}{k \choose r}</math> possible choices such <math>R</math>. For any fixed choice of <math>R</math>, the probability that an edge picked by a vertex in <math>S-R</math> connects to a vertex in <math>S</math> is at most <math>k/n</math>, and there are <math>d(k-r)</math> such edges. For any fixed <math>S</math> of size <math>k</math> and <math>R</math> of size <math>r</math>, the probability that all neighbors of all vertices in <math>S-R</math> are in <math>S</math> is at most <math>\left(\frac{k}{n}\right)^{d(k-r)}</math>. Due to the union bound, for any fixed <math>S</math> of size <math>k</math>,
| |
| :<math>
| |
| \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}
| |
| </math>
| |
| Therefore,
| |
| :<math>
| |
| \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}
| |
| </math>
| |
| The last line is <math>o(1)</math> when <math>d\ge\frac{2}{1-\alpha}</math>. Therefore, <math>G</math> is an expander graph with expansion ratio <math>\alpha</math> with high probability for suitable choices of constant <math>d</math> and constant <math>\alpha</math>.
| |
| | |
| == 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 <math>G</math>, the vertex set <math>S\subset V</math> which has low expansion ratio is a proof of the fact that <math>G</math> is not an expander, which can be verified in poly-time. However, there is no efficient algorithm for computing the <math>\phi(G)</math> unless '''NP'''='''P'''.
| |
| | |
| The expansion ratio of a graph is closely related to the [http://en.wikipedia.org/wiki/Cut_(graph_theory)#Sparsest_cut sparsest cut] of the graph, which is the dual problem of the [http://en.wikipedia.org/wiki/Multi-commodity_flow_problem 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.
| |
| | |
| = Spectral Graph Theory=
| |
| == Graph spectrum==
| |
| The '''adjacency matrix''' of an <math>n</math>-vertex graph <math>G</math>, denoted <math>A = A(G)</math>, is an <math>n\times n</math> matrix where <math>A(u,v)</math> is the number of edges in <math>G</math> between vertex <math>u</math> and vertex <math>v</math>. Because <math>A</math> is a symmetric matrix with real entries, due to the [http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem Perron-Frobenius theorem], it has real eigenvalues <math>\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math>, which associate with an orthonormal system of eigenvectors <math>v_1,v_2,\ldots, v_n\,</math> with <math>Av_i=\lambda_i v_i\,</math>. We call the eigenvalues of <math>A</math> the '''spectrum''' of the graph <math>G</math>.
| |
| | |
| The spectrum of a graph contains a lot of information about the graph. For example, supposed that <math>G</math> is <math>d</math>-regular, the following lemma holds.
| |
| {{Theorem
| |
| |Lemma|
| |
| # <math>|\lambda_i|\le d</math> for all <math>1\le i\le n</math>.
| |
| # <math>\lambda_1=d</math> and the corresponding eigenvector is <math>(\frac{1}{\sqrt{n}},\frac{1}{\sqrt{n}},\ldots,\frac{1}{\sqrt{n}})</math>.
| |
| # <math>G</math> is connected if and only if <math>\lambda_1>\lambda_2</math>.
| |
| # If <math>G</math> is bipartite then <math>\lambda_1=-\lambda_n</math>.
| |
| }}
| |
| {{Proof| Let <math>A</math> be the adjacency matrix of <math>G</math>, with entries <math>a_{ij}</math>. It is obvious that <math>\sum_{j}a_{ij}=d\,</math> for any <math>j</math>.
| |
| *(1) Suppose that <math>Ax=\lambda x, x\neq \mathbf{0}</math>, and let <math>x_i</math> be an entry of <math>x</math> with the largest absolute value. Since <math>(Ax)_i=\lambda x_i</math>, we have
| |
| ::<math>
| |
| \sum_{j}a_{ij}x_j=\lambda x_i,\,
| |
| </math>
| |
| :and so
| |
| ::<math>
| |
| |\lambda||x_i|=\left|\sum_{j}a_{ij}x_j\right|\le \sum_{j}a_{ij}|x_j|\le \sum_{j}a_{ij}|x_i| \le d|x_i|.
| |
| </math>
| |
| :Thus <math>|\lambda|\le d</math>. | |
| *(2) is easy to check. | |
| *(3) Let <math>x</math> be the nonzero vector for which <math>Ax=dx</math>, and let <math>x_i</math> be an entry of <math>x</math> with the largest absolute value. Since <math>(Ax)_i=d x_i</math>, we have
| |
| ::<math>
| |
| \sum_{j}a_{ij}x_j=d x_i.\,
| |
| </math>
| |
| :Since <math>\sum_{j}a_{ij}=d\,</math> and by the maximality of <math>x_i</math>, it follows that <math>x_j=x_i</math> for all <math>j</math> that <math>a_{ij}>0</math>. Thus, <math>x_i=x_j</math> if <math>i</math> and <math>j</math> are adjacent, which implies that <math>x_i=x_j</math> if <math>i</math> and <math>j</math> are connected. For connected <math>G</math>, all vertices are connected, thus all <math>x_i</math> are equal. This shows that if <math>G</math> is connected, the eigenvalue <math>d=\lambda_1</math> has multiplicity 1, thus <math>\lambda_1>\lambda_2</math>.
| |
| | |
| :If otherwise, <math>G</math> is disconnected, then for two different components, we have <math>Ax=dx</math> and <math>Ay=dy</math>, where the entries of <math>x</math> and <math>y</math> are nonzero only for the vertices in their components components. Then <math>A(\alpha x+\beta y)=d(\alpha x+\beta y)</math>. Thus, the multiplicity of <math>d</math> is greater than 1, so <math>\lambda_1=\lambda_2</math>.
| |
| | |
| *(4) If <math>G</math> if bipartite, then the vertex set can be partitioned into two disjoint nonempty sets <math>V_1</math> and <math>V_2</math> such that all edges have one endpoint in each of <math>V_1</math> and <math>V_2</math>. Algebraically, this means that the adjacency matrix can be organized into the form | |
| ::<math>
| |
| P^TAP=\begin{bmatrix}
| |
| 0 & B\\
| |
| B^T & 0
| |
| \end{bmatrix}
| |
| </math>
| |
| :where <math>P</math> is a permutation matrix, which has no change on the eigenvalues.
| |
| :If <math>x</math> is an eigenvector corresponding to the eigenvalue <math>\lambda</math>, then <math>x'</math> which is obtained from <math>x</math> by changing the sign of the entries corresponding to vertices in <math>V_2</math>, is an eigenvector corresponding to the eigenvalue <math>-\lambda</math>. It follows that the spectrum of a bipartite graph is symmetric with respect to 0.
| |
| }}
| |
| | |
| == Cheeger's Inequality ==
| |
| One of the most exciting results in spectral graph theory is the following theorem which relate the graph expansion to the spectral gap.
| |
| {{Theorem
| |
| |Theorem (Cheeger's inequality)|
| |
| :Let <math>G</math> be a <math>d</math>-regular graph with spectrum <math>\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math>. Then
| |
| ::<math>
| |
| \frac{d-\lambda_2}{2}\le \phi(G) \le \sqrt{2d(d-\lambda_2)}.
| |
| </math>
| |
| }}
| |
| The theorem was first stated for Riemannian manifolds, and was proved by Cheeger and Buser (for different directions of the inequalities). The discrete case is proved independently by Dodziuk and Alon-Milman.
| |
| | |
| For a <math>d</math>-regular graph, the quantity <math>(d-\lambda_2)</math> is called the '''spectral gap'''. The name is due to the fact that it is the gap between the first and the second largest eigenvalues of a graph.
| |
| | |
| If we write <math>\alpha=1-\frac{\lambda_2}{d}</math> (sometimes it is called the normalized spectral gap), the Cheeger's inequality is turned into a nicer form:
| |
| :<math>
| |
| \frac{\alpha}{2}\le \frac{\phi}{d}\le\sqrt{2\alpha} </math> or equivalently <math>
| |
| \frac{1}{2}\left(\frac{\phi}{d}\right)^2\le \alpha\le 2\left(\frac{\phi}{d}\right)
| |
| </math>.
| |
| | |
| === Optimization Characterization of Eigenvalues ===
| |
| {{Theorem
| |
| |Theorem (Rayleigh-Ritz theorem)|
| |
| :Let <math>A</math> be a symmetric <math>n\times n</math> matrix. Let <math>\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math> be the eigen values of <math>A</math> and <math>v_1,v_2,\ldots,v_n</math> be the corresponding eigenvectors. Then
| |
| ::<math>
| |
| \begin{align}
| |
| \lambda_1
| |
| &=\max_{x\in\mathbb{R}^n}\frac{x^TAx}{x^Tx}
| |
| \end{align}
| |
| </math> and <math>
| |
| \begin{align}
| |
| \lambda_2
| |
| &=\max_{x\bot v_1}\frac{x^TAx}{x^Tx}.
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| {{Proof|
| |
| Without loss of generality, we may assume that <math>v_1,v_2,\ldots,v_n</math> are orthonormal eigen-basis.
| |
| Then it holds that
| |
| :<math>\frac{v_1^TAv_1}{v_1^Tv_1}=\lambda_1v_1^Tv_1=\lambda_1</math>,
| |
| thus we have <math>\max_{x\in\mathbb{R}^n}\frac{x^TAx}{x^Tx}\ge\lambda_1</math>.
| |
| | |
| Let <math>x\in\mathbb{R}^n</math> be an arbitrary vector and let <math>y=\frac{x}{\sqrt{x^Tx}}=\frac{x}{\|x\|}</math> be its normalization.
| |
| Since <math>v_1,v_2,\ldots,v_n</math> are orthonormal basis, <math>y</math> can be expressed as <math>y=\sum_{i=1}^nc_iv_i</math>. Then
| |
| :<math>
| |
| \begin{align}
| |
| \frac{x^TAx}{x^Tx}
| |
| &=y^TAy
| |
| =\left(\sum_{i=1}^nc_iv_i\right)^TA\left(\sum_{i=1}^nc_iv_i\right)
| |
| =\left(\sum_{i=1}^nc_iv_i\right)^T\left(\sum_{i=1}^n\lambda_ic_iv_i\right)\\
| |
| &=\sum_{i=1}^n\lambda_ic_i^2
| |
| \le\lambda_1\sum_{i=1}^nc_i^2
| |
| =\lambda_1\|y\|
| |
| =\lambda_1.
| |
| \end{align}
| |
| </math>
| |
| Therefore, <math>\max_{x\in\mathbb{R}^n}\frac{x^TAx}{x^Tx}\le\lambda_1</math>. Altogether we have <math>\max_{x\in\mathbb{R}^n}\frac{x^TAx}{x^Tx}=\lambda_1</math>
| |
| | |
| It is similar to prove <math>\max_{x\bot v_1}\frac{x^TAx}{x^Tx}=\lambda_2</math>. In the first part take <math>x=v_2</math> to show that <math>\max_{x\bot v_1}\frac{x^TAx}{x^Tx}\ge\lambda_2</math>; and in the second part take an arbitrary <math>x\bot v_1</math> and <math>y=\frac{x}{\|x\|}</math>. Notice that <math>y\bot v_1</math>, thus <math>y=\sum_{i=1}^nc_iv_i</math> with <math>c_1=0</math>.
| |
| }}
| |
| | |
| The Rayleigh-Ritz Theorem is a special case of a fundamental theorem in linear algebra, called the [http://en.wikipedia.org/wiki/Min-max_theorem Courant-Fischer theorem], which characterizes the eigenvalues of a symmetric matrix by a series of optimizations:
| |
| {{Theorem
| |
| |Theorem (Courant-Fischer theorem)|
| |
| :Let <math>A</math> be a symmetric matrix with eigenvalues <math>\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math>. Then
| |
| ::<math>
| |
| \begin{align}
| |
| \lambda_k
| |
| &=\max_{v_1,v_2,\ldots,v_{n-k}\in \mathbb{R}^n}\min_{\overset{x\in\mathbb{R}^n, x\neq \mathbf{0}}{x\bot v_1,v_2,\ldots,v_{n-k}}}\frac{x^TAx}{x^Tx}\\
| |
| &=
| |
| \min_{v_1,v_2,\ldots,v_{k-1}\in \mathbb{R}^n}\max_{\overset{x\in\mathbb{R}^n, x\neq \mathbf{0}}{x\bot v_1,v_2,\ldots,v_{k-1}}}\frac{x^TAx}{x^Tx}.
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| | |
| === Graph Laplacian ===
| |
| Let <math>G(V,E)</math> be a <math>d</math>-regular graph of <math>n</math> vertices and let <math>A</math> be its adjacency matrix. We define <math>L=dI-A</math> to be the '''Laplacian''' of the graph <math>G</math>. Take <math>x\in \mathbb{R}^V</math> as a distribution over vertices, its Laplacian quadratic form <math>x^TLx</math> measures the "smoothness" of <math>x</math> over the graph topology, just as what the [http://en.wikipedia.org/wiki/Laplace_operator Laplacian operator] does to the differentiable functions.
| |
| | |
| {{Theorem|Laplacian Property|
| |
| :For any vector <math>x\in\mathbb{R}^n</math>, it holds that
| |
| ::<math>x^TLx=\sum_{uv\in E}(x_u-x_v)^2</math>.
| |
| }}
| |
| {{Proof|
| |
| :<math>\begin{align}
| |
| x^TLx
| |
| &=
| |
| \sum_{u,v\in V}x_u(dI-A)_{uv}x_v\\
| |
| &=
| |
| \sum_{u}\left(dx_u^2-\sum_{uv\in E}x_ux_v\right)\\
| |
| &=
| |
| \sum_{u\in V}\sum_{uv\in E}(x_u^2-x_ux_v).
| |
| \end{align}
| |
| </math>
| |
| On the other hand,
| |
| :<math>
| |
| \begin{align}
| |
| \sum_{uv\in E}(x_u-x_v)^2
| |
| &=
| |
| \sum_{uv\in E}\left(x_u^2-2x_ux_v+x_v^2\right)\\
| |
| &=
| |
| \sum_{uv\in E}\left((x_u^2-x_ux_v)+(x_v^2-x_vx_u)\right)\\
| |
| &=
| |
| \sum_{u\in V}\sum_{uv\in E}(x_u^2-x_ux_v).
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| | |
| Applying the Rayleigh-Ritz theorem to the Laplacian matrix of the graph, we have the following "variational characterization" of the spectral gap <math>d-\lambda_2</math>.
| |
| | |
| {{Theorem
| |
| |Theorem (Variational Characterization)|
| |
| :Let <math>G(V,E)</math> be a <math>d</math>-regular graph of <math>n</math> vertices. Suppose that its adjacency matrix is <math>A</math>, whose eigenvalues are <math>\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math>. Let <math>L=dI-A</math> be the Laplacian matrix. Then
| |
| ::<math>
| |
| \begin{align}
| |
| d-\lambda_2
| |
| &=\min_{x\bot \boldsymbol{1}}\frac{x^TLx}{x^Tx}
| |
| =\min_{x\bot \boldsymbol{1}}\frac{\sum_{uv\in E}(x_u-x_v)^2}{\sum_{v\in V}x_v^2}.
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| {{proof|
| |
| For <math>d</math>-regular graph, we know that <math>\lambda_1=d</math> and <math>\boldsymbol{1}A=d\boldsymbol{1}</math>, thus <math>\boldsymbol{1}</math> is the eigenvector of <math>\lambda_1</math>. Due to Rayleigh-Ritz Theorem, it holds that <math>\lambda_2
| |
| =\max_{x\bot \boldsymbol{1}}\frac{x^TAx}{x^Tx}</math>. Then
| |
| :<math>
| |
| \begin{align}
| |
| \min_{x\bot \boldsymbol{1}}\frac{x^TLx}{x^Tx}
| |
| &=\min_{x\bot \boldsymbol{1}}\frac{x^T(dI-A)x}{x^Tx}\\
| |
| &=\min_{x\bot \boldsymbol{1}}\frac{dx^Tx-x^TAx}{x^Tx}\\
| |
| &=\min_{x\bot \boldsymbol{1}}\left(d-\frac{x^TAx}{x^Tx}\right)\\
| |
| &=d-\max_{x\bot \boldsymbol{1}}\frac{x^TAx}{x^Tx}\\
| |
| &=d-\lambda_2.
| |
| \end{align}
| |
| </math>
| |
| We know it holds for the graph Laplacian that <math>x^TLx=\sum_{uv\in E}(x_u-x_v)^2</math>. So the variational characterization of the second eigenvalue of graph is proved.
| |
| }}
| |
| | |
| === Proof of Cheeger's Inequality ===
| |
| We will first give an informal explanation why Cheeger's inequality holds.
| |
| | |
| Recall that the expansion is defined as
| |
| :<math>
| |
| \phi(G)=\min_{\overset{S\subset V}{|S|\le\frac{n}{2}}}\frac{|\partial S|}{|S|}.
| |
| </math>
| |
| Let <math>\chi_S</math> be the '''characteristic vector''' of the set <math>S</math> such that
| |
| :<math>\chi_S(v)=\begin{cases}
| |
| 1 & v\in S,\\ | |
| 0 & v\not\in S.
| |
| \end{cases}</math>
| |
| It is easy to see that
| |
| :<math>
| |
| \frac{\sum_{uv\in E}(\chi_S(u)-\chi_S(v))^2}{\sum_{v\in V}\chi_S(v)^2}=\frac{|\partial S|}{|S|}.
| |
| </math>
| |
| Thus, the expansion can be expressed algebraically as
| |
| :<math>
| |
| \phi(G)=\min_{\overset{S\subset V}{|S|\le\frac{n}{2}}}\frac{\sum_{uv\in E}(\chi_S(u)-\chi_S(v))^2}{\sum_{v\in V}\chi_S(v)^2}=\min_{\overset{x\in\{0,1\}^n}{\|x\|_1\le\frac{n}{2}}}\frac{\sum_{uv\in E}(x_u-x_v)^2}{\sum_{v\in V}x_v^2}.
| |
| </math>
| |
| On the other hand, due to the variational characterization of the spectral gap, we have
| |
| :<math>
| |
| d-\lambda_2=\min_{x\bot\boldsymbol{1}}\frac{\sum_{uv\in E}(x_u-x_v)^2}{\sum_{v\in V}x_v^2}.
| |
| </math>
| |
| | |
| We can easily observe the similarity between the two formulas. Both the expansion ration <math>\phi(G)</math> and the spectral gap <math>d-\lambda_2</math> can be characterized by optimizations of the same objective function <math>\frac{\sum_{uv\in E}(x_u-x_v)^2}{\sum_{v\in V}x_v^2}</math> over different domains (for the spectral gap, the optimization is over all <math>x\bot\boldsymbol{1}</math>; and for the expansion ratio, it is over all such vectors <math>x\in\{0,1\}^n</math> with at most <math>n/2</math> many 1-entries).
| |
| | |
| -------
| |
| ;Notations
| |
| Throughout the proof, we assume that <math>G(V,E)</math> is the <math>d</math>-regular graph of <math>n</math> vertices, <math>A</math> is the adjacency matrix, whose eigenvalues are <math>\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math>, and <math>L=(dI-A)</math> is the graph Laplacian.
| |
| | |
| ==== Large spectral gap implies high expansion ====
| |
| {{Theorem
| |
| |Cheeger's inequality (lower bound)|
| |
| :<math>
| |
| \phi(G)\ge\frac{d-\lambda_2}{2}.
| |
| </math>
| |
| }}
| |
| {{Proof|
| |
| Let <math>S^*\subset V</math>, <math>|S^*|\le\frac{n}{2}</math>, be the vertex set achieving the optimal expansion ratio <math>\phi(G)=\min_{\overset{S\subset V}{|S|\le\frac{n}{2}}} \frac{|\partial S|}{|S|}=\frac{|\partial S^*|}{|S^*|}</math>, and <math>x\in\mathbb{R}^n</math> be a vector defined as
| |
| :<math>
| |
| x_v=\begin{cases}
| |
| 1/|S^*| & \text{if } v\in S^*,\\
| |
| -1/\left|\overline{S^*}\right| &\text{if }v\in\overline{S^*}.
| |
| \end{cases}
| |
| </math>
| |
| Clearly, <math>x\cdot \boldsymbol{1}=\sum_{v\in S^*}\frac{1}{|S^*|} -\sum_{v\in\overline{S^*}}\frac{1}{\left|\overline{S^*}\right|}=0</math>, thus <math>x\bot\boldsymbol{1}</math>.
| |
| | |
| Due to the variational characterization of the second eigenvalue,
| |
| :<math>
| |
| \begin{align}
| |
| d-\lambda_2
| |
| &\le\frac{\sum_{uv\in E}(x_u-x_v)^2}{\sum_{v\in V}x_v^2}\\
| |
| &=\frac{\sum_{u\in S^*,v\in\overline{S^*},uv\in E}\left(1/|S^*|+1/|\overline{S^*}|\right)^2}{1/|S^*|+1/|\overline{S^*}|}\\
| |
| &=\left(\frac{1}{|S^*|}+\frac{1}{\left|\overline{S^*}\right|}\right)\cdot|\partial S^*|\\
| |
| &\le \frac{2|\partial S^*|}{|S^*|} &(\text{since }|S^*|\le\frac{n}{2})\\
| |
| &=2\phi(G).
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| | |
| ==== High expansion implies large spectral gap ====
| |
| We next prove the upper bound direction of the Cheeger's inequality:
| |
| {{Theorem|Cheeger's inequality (upper bound)|
| |
| :<math>
| |
| \phi(G) \le \sqrt{2d(d-\lambda_2)}.
| |
| </math>
| |
| }}
| |
| | |
| This direction is harder than the lower bound direction. But it is mathematically more interesting and also more useful to us for analyzing the mixing time of random walks.
| |
| | |
| We prove the following equivalent inequality:
| |
| :<math>
| |
| \frac{\phi^2}{2d} \le d-\lambda_2.
| |
| </math>
| |
| | |
| Let <math>x</math> satisfy that
| |
| * <math>Ax=\lambda_2x</math>, i.e., it is a eigenvector for <math>\lambda_2</math>;
| |
| * <math>|\{v\in V\mid x_v>0\}|\le\frac{n}{2}</math>, i.e., <math>x</math> has at most <math>n/2</math> positive entries. (We can always choose <math>x</math> to be <math>-x</math> if this is not satisfied.)
| |
| And let nonnegative vector <math>y</math> be defined as
| |
| :<math>y_v=\begin{cases}
| |
| x_v & x_v>0,\\
| |
| 0 & \text{otherwise.}
| |
| \end{cases}</math>
| |
| We then prove the following inequalities:
| |
| # <math>\frac{y^TLy}{y^Ty}\le d-\lambda_2</math>;
| |
| # <math>\frac{\phi^2}{2d}\le\frac{y^TLy}{y^Ty}</math>.
| |
| The theorem is then a simple consequence by combining these two inequalities.
| |
| | |
| We prove the first inequality:
| |
| {{Theorem|Lemma|
| |
| :<math>\frac{y^TLy}{y^Ty}\le d-\lambda_2</math>.
| |
| }}
| |
| {{Proof|
| |
| If <math>x_u\ge 0</math>, then
| |
| :<math>
| |
| \begin{align}
| |
| (Ly)_u
| |
| &=((dI-A)y)_u
| |
| =dy_u-\sum_{v}A(u,v)y_v
| |
| =dx_u-\sum_{v:x_v\ge 0}A(u,v)x_v\\
| |
| &\le dx_u-\sum_{v}A(u,v)x_v
| |
| =((dI-A)x)_u
| |
| =(d-\lambda_2)x_u.
| |
| \end{align}
| |
| </math>
| |
| Then
| |
| :<math>
| |
| \begin{align}
| |
| y^TLy
| |
| &=\sum_{u}y_u(Ly)_u
| |
| =\sum_{u:x_u\ge 0}y_u(Ly)_u
| |
| =\sum_{u:x_u\ge 0}x_u(Ly)_u\\
| |
| &\le (d-\lambda_2)\sum_{u:x_u\ge 0}x_u^2
| |
| =(d-\lambda_2)\sum_{u}y_u^2
| |
| =(d-\lambda_2)y^Ty,
| |
| \end{align}
| |
| </math>
| |
| which proves the lemma.
| |
| }}
| |
| | |
| We then prove the second inequality:
| |
| {{Theorem|Lemma|
| |
| :<math>\frac{\phi^2}{2d}\le\frac{y^TLy}{y^Ty}</math>.
| |
| }}
| |
| {{Proof|
| |
| To prove this, we introduce a new quantity <math>\frac{\sum_{uv\in E}|y_u^2-y_v^2|}{y^Ty}</math> and shows that
| |
| :<math>\phi\le\frac{\sum_{uv\in E}|y_u^2-y_v^2|}{y^Ty}\le\sqrt{2d}\cdot\sqrt{\frac{y^TLy}{y^Ty}}</math>.
| |
| This will give us the desired inequality <math>\frac{\phi^2}{2d}\le\frac{y^TLy}{y^Ty}</math>.
| |
| | |
| {{Theorem|Lemma|
| |
| :<math>\frac{\sum_{uv\in E}|y_u^2-y_v^2|}{y^Ty}\le\sqrt{2d}\cdot\sqrt{\frac{y^TLy}{y^Ty}}</math>.
| |
| }}
| |
| {{Proof|
| |
| By the Cauchy-Schwarz Inequality,
| |
| :<math>
| |
| \begin{align}
| |
| \sum_{uv\in E}|y_u^2-y_v^2|
| |
| &=\sum_{uv\in E}|y_u-y_v||y_u+y_v|\\
| |
| &\le\sqrt{\sum_{uv\in E}(y_u-y_v)^2}\cdot\sqrt{\sum_{uv\in E}(y_u+y_v)^2}.
| |
| \end{align}
| |
| </math>
| |
| By the Laplacian property, the first term <math>\sqrt{\sum_{uv\in E}(y_u-y_v)^2}=\sqrt{y^TLy}</math>. By the Inequality of Arithmetic and Geometric Means, the second term
| |
| :<math>
| |
| \sqrt{\sum_{uv\in E}(y_u+y_v)^2}
| |
| \le\sqrt{2\sum_{uv\in E}(y_u^2+y_v^2)}
| |
| =\sqrt{2d\sum_{u\in V}y_u^2}
| |
| =\sqrt{2dy^Ty}.
| |
| </math>
| |
| Combining them together, we have
| |
| :<math>\sum_{uv\in E}|y_u^2-y_v^2|\le\sqrt{2d}\cdot\sqrt{y^TLy}\cdot\sqrt{y^Ty}</math>.
| |
| }}
| |
| | |
| {{Theorem|Lemma|
| |
| :<math>\phi\le\frac{\sum_{uv\in E}|y_u^2-y_v^2|}{y^Ty}</math>.
| |
| }}
| |
| {{Proof|
| |
| Suppose that <math>y</math> has <math>t</math> nonzero entries. We know that <math>t\le n/2</math> due to the definition of <math>y</math>. We enumerate the vertices <math>u_1,u_2,\ldots,u_n\in V</math> such that
| |
| :<math>y_{u_1}\ge y_{u_2}\ge\cdots\ge y_{u_t}>y_{u_{t+1}}=\cdots=y_{u_n}=0</math>.
| |
| Then
| |
| :<math>
| |
| \begin{align}
| |
| \sum_{uv\in E}|y_u^2-y_v^2|
| |
| &=\sum_{u_iu_j\in E\atop i<j}(y_{u_i}^2-y_{u_j}^2)
| |
| =\sum_{u_iu_j\in E\atop i<j}\sum_{k=i}^{j-1}(y_{u_k}^2-y_{u_{k+1}}^2)\\
| |
| &=\sum_{i=1}^n\sum_{j>i}A(u_i,u_j)\sum_{k=i}^{j-1}(y_{u_k}^2-y_{u_{k+1}}^2)
| |
| =\sum_{i=1}^n\sum_{j>i}\sum_{k=i}^{j-1}A(u_i,u_j)(y_{u_k}^2-y_{u_{k+1}}^2).
| |
| \end{align}
| |
| </math>
| |
| We have the following universal equation for sums:
| |
| :<math>
| |
| \begin{align}
| |
| \sum_{i=1}^n\sum_{j>i}\sum_{k=i}^{j-1}A(u_i,u_j)(y_{u_k}^2-y_{u_{k+1}}^2)
| |
| &=\sum_{k=1}^n\sum_{i\le k}\sum_{j>k}A(u_i,u_j)(y_{u_k}^2-y_{u_{k+1}}^2)\\
| |
| &=\sum_{k=1}^t(y_{u_k}^2-y_{u_{k+1}}^2)\sum_{i\le k}\sum_{j>k}A(u_i,u_j)
| |
| \end{align}
| |
| </math>
| |
| Notice that <math>\sum_{i\le k}\sum_{j>k}A(u_i,u_j)=|\partial\{u_1,\ldots, u_k\}|</math>, which is at most <math>\phi k</math> since <math>k\le t\le n/2</math>. Therefore, combining these together, we have
| |
| :<math>
| |
| \begin{align}
| |
| \sum_{uv\in E}|y_u^2-y_v^2|
| |
| &=\sum_{k=1}^t(y_{u_k}^2-y_{u_{k+1}}^2)\sum_{i\le k}\sum_{j>k}A(u_i,u_j)\\
| |
| &=\sum_{k=1}^t(y_{u_k}^2-y_{u_{k+1}}^2)|\partial\{u_1,\ldots, u_k\}|\\
| |
| &\le \phi\sum_{k=1}^t(y_{u_k}^2-y_{u_{k+1}}^2)k\\
| |
| &=\phi\sum_{k=1}^ty_{u_k}^2\\
| |
| &=\phi y^Ty.
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| }}
| |