高级算法 (Fall 2023)/Problem Set 2

• 本次作业每个Problem分值10分，满分80分。

• 每道题目的解答都要有完整的解题过程，中英文不限。

• 我们推荐大家使用LaTeX, markdown等对作业进行排版。

Problem 1 (Adjacency matrix)

Let [math]\displaystyle{ A }[/math] be the adjacency matrix of an undirected connected graph [math]\displaystyle{ G }[/math], and [math]\displaystyle{ \alpha_1 }[/math] be its largest eigenvalue.

• [Lowerbounding [math]\displaystyle{ \alpha_1 }[/math]] We proved [math]\displaystyle{ \alpha_1 \le d_{\mathrm{max}} }[/math] in class. Show that [math]\displaystyle{ \alpha_1 \ge d_{\mathrm{avg}} }[/math] where [math]\displaystyle{ d_{\mathrm{avg}}:=\frac{2|E|}{|V|} }[/math] is the average degree of the graph.

• [Monotonicity of the spectrum] Let [math]\displaystyle{ A' }[/math] be the adjacency matrix of any subgraph of [math]\displaystyle{ A }[/math] produced by deleting vertices, and let [math]\displaystyle{ \alpha_1' }[/math] be the largest eigenvalue of [math]\displaystyle{ A' }[/math]. Show that [math]\displaystyle{ \alpha'_1\leq \alpha_1 }[/math].

• [Chromatic number] The chromatic number [math]\displaystyle{ \chi(G) }[/math] of a graph is the smallest number of colors needed to color the vertices of [math]\displaystyle{ G }[/math] so that no two adjacent vertices share same color. Prove that [math]\displaystyle{ \chi(G) \le \lfloor \alpha_1 \rfloor +1 }[/math].

Problem 2 (Graph Laplacian)

• [Spectrum of special graphs] Find eigenvalues of the Laplacian matrices of the following graphs:
  1. The complete graph with [math]\displaystyle{ n }[/math] vertices.
  2. The star graph with [math]\displaystyle{ n }[/math] vertices.

• [Number of connected components] Let [math]\displaystyle{ G }[/math] be an undirected graph, and [math]\displaystyle{ \lambda_1\le \lambda_2 \le \ldots \le \lambda_n }[/math] be the eigenvalues of its Laplacian matrix [math]\displaystyle{ {L} }[/math]. Prove that [math]\displaystyle{ \lambda_k = 0 }[/math] if and only if [math]\displaystyle{ G }[/math] has at least [math]\displaystyle{ k }[/math] connected components.

• [Lowerbounding [math]\displaystyle{ \lambda_2 }[/math]] Let [math]\displaystyle{ G }[/math] be an undirected graph whose Laplacian is [math]\displaystyle{ L }[/math], with second-smallest eigenvalue [math]\displaystyle{ \lambda_2 }[/math]. We know that if [math]\displaystyle{ G }[/math] is connected then [math]\displaystyle{ \lambda_2\gt 0 }[/math]. Prove that [math]\displaystyle{ \lambda_2 \geq \Omega\left(\frac{1}{rn}\right) \geq \Omega(1/n^2) }[/math] by analyzing the Rayleigh quotient on all test vectors [math]\displaystyle{ x\perp \mathbf{1} }[/math]. Here, [math]\displaystyle{ r }[/math] is the diameter of the graph (i.e. the maximum shortest-path distance between pairs of vertices in the graph). Further, show that when [math]\displaystyle{ G }[/math] is simple and [math]\displaystyle{ d }[/math]-regular, we have [math]\displaystyle{ \lambda_2 \geq \Omega(d/n^2) }[/math].

Problem 3 (Cheeger-type inequality)

The Cheeger's inequality for graphs provides a relationship between the conductance of the graph and the second smallest eigenvalue of its normalized Laplacian matrix. In this problem, you will discover a Cheeger type inequality for the largest eigenvalue [math]\displaystyle{ \lambda_n }[/math].

(1) Prove: Let [math]\displaystyle{ G = (V, E) }[/math] be an undirected graph and [math]\displaystyle{ \lambda_n }[/math] be the largest eigenvalue of normalized Laplacian [math]\displaystyle{ \mathcal L(G) }[/math]. Then

[math]\displaystyle{ 2 - \lambda_n = \min_{x \in \mathbb R^n} \frac{\sum _{ij \in E} (x_i + x_j)^2}{\sum _{i \in V} d_i\cdot x_i^2}. }[/math]

(2) Let [math]\displaystyle{ S \subseteq V (G) }[/math] be a bipartite component with partition [math]\displaystyle{ S = (L, R) }[/math] such that all the edges in [math]\displaystyle{ S }[/math] are between [math]\displaystyle{ L }[/math] and [math]\displaystyle{ R }[/math]. Then the vector [math]\displaystyle{ \boldsymbol{x} \in \{−1, 0, 1\}^n }[/math] is a solution to the above optimization problem with objective value [math]\displaystyle{ 0 }[/math], where

[math]\displaystyle{ \boldsymbol x_i = \begin{cases}+1 & \text { if } i \in L \\ -1 & \text { if } i \in R \\ 0 & \text { otherwise }\end{cases} }[/math]

Using this association between a vector [math]\displaystyle{ \boldsymbol x \in \{−1, 0, 1\}^n }[/math] and a bipartition of a subset [math]\displaystyle{ S = (L, R) }[/math] , we consider the following denition of the bipartiteness ratio [math]\displaystyle{ \beta(x) }[/math] of [math]\displaystyle{ S = (L, R) }[/math] where each edge within [math]\displaystyle{ L }[/math] and each edge within [math]\displaystyle{ R }[/math] contributes [math]\displaystyle{ 2 }[/math] in the numerator [math]\displaystyle{ \beta(x) := \frac{\sum _{\{i,j\} \in E} |x_i + x_j|}{\sum _{i \in V} d_i|x_i|}. }[/math] The bipartiteness ratio of a graph [math]\displaystyle{ G }[/math] is defined as [math]\displaystyle{ \beta(G):= \min_{\boldsymbol x\neq \boldsymbol{0} \atop \boldsymbol x\in \{-1,0,1\}^n} \beta(x) }[/math].

Show the following analog of Cheeger's inequality for [math]\displaystyle{ 2 − \lambda_n }[/math] and [math]\displaystyle{ \beta(G) }[/math]:

[math]\displaystyle{ \frac{1}{2}(2 - \lambda_n) \le \beta(G) \le \sqrt{2(2 - \lambda_n)}. }[/math]

Problem 4 (Random walk on graph)

In class, we showed that large conductance implies rapid mixing of random walks. In this problem, we show that this is also necessary to some extent.

Consider an undirected, unweighted graph [math]\displaystyle{ G = (V,E) }[/math] with [math]\displaystyle{ |V|=n }[/math]. Let [math]\displaystyle{ \pi }[/math] be the stationary distribution of the simple random walk on [math]\displaystyle{ V }[/math].

(1) Prove that the conductance [math]\displaystyle{ \phi(S) }[/math] can be interpreted as [math]\displaystyle{ \mathbf{Pr}{ [X_1 \not\in S | X_0 \sim \pi_S ] } }[/math], the probability that a random walk started at [math]\displaystyle{ X_0 }[/math] drawn according to [math]\displaystyle{ \pi }[/math] restricted to [math]\displaystyle{ S }[/math], escapes from [math]\displaystyle{ S }[/math] in one step.

(2) Further, if [math]\displaystyle{ G }[/math] is a regular graph and the adjacency matrix [math]\displaystyle{ A }[/math] of [math]\displaystyle{ G }[/math] is positive semi-definite (PSD), show that [math]\displaystyle{ \mathbf{Pr}{[X_t \in S | X_0 \sim \pi_S]} \ge (1- \phi(S))^t }[/math] for all [math]\displaystyle{ t\geq 1 }[/math] and [math]\displaystyle{ t\in \mathbb{N} }[/math]. (Hint:first show that [math]\displaystyle{ \langle x,A^t x \rangle\geq \langle x,Ax \rangle^t }[/math] if [math]\displaystyle{ A }[/math] is PSD.)

(3) The [math]\displaystyle{ \ell_2 }[/math] mixing time of the random walk over [math]\displaystyle{ n }[/math] items with distribution [math]\displaystyle{ \{p^{(t)}\}_{t\geq 0} }[/math] is defined as the smallest [math]\displaystyle{ t }[/math] such that

[math]\displaystyle{ \left\|\frac{p^{(t)}}{\pi} - 1\right\|_{2,\pi}^2 :=\sum_{i=1}^n \pi_i \left(\frac{p_i^{(t)}}{\pi_i} - 1\right)^2 \leq \frac{1}{4}, \quad \forall p^{(0)}. }[/math]

In the context of (2), suppose there exists a [math]\displaystyle{ S\subseteq V }[/math] such that [math]\displaystyle{ \pi(S) :=\sum_{v\in S}\pi(v) = \frac{1}{\sqrt{n}} }[/math], then show that [math]\displaystyle{ \ell_2 }[/math] mixing time of [math]\displaystyle{ \{X_i\}_{i\geq 0} }[/math] is at least [math]\displaystyle{ \Omega\left(\frac{\log(n)}{\phi(S)}\right) }[/math] if [math]\displaystyle{ {\phi(S)}\ll 1 }[/math].

Problem 5 (Hitting time, commute time)

Consider inserting an edge to an undirected graph. Prove or disprove the following monotonicity:

(1) The hitting times between any two vertices are monotone with respect to inserting any edge. That is to say, after inserting any edge, either the hitting times between any two vertices do not increase or the hitting times between any two vertices do not decrease.

(2) Fix any vertex [math]\displaystyle{ t }[/math]. The hitting times from any other vertex to [math]\displaystyle{ t }[/math] are monotone with respect to inserting an edge incident on [math]\displaystyle{ t }[/math].

(3) The commute times between any two vertices are monotone with respect to inserting any edge.

Problem 6 (Electrical network)

• [bounding effective resistance] Let [math]\displaystyle{ s,t (s\neq t) }[/math] be any two vertices in any connected unweighted graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices.
  1. What is the minimum possible value of [math]\displaystyle{ R_{\mathrm{eff}}(s,t) }[/math]? Why?
  2. What is the maximum possible value of [math]\displaystyle{ R_{\mathrm{eff}}(s,t) }[/math]? Why?
• [Triangle inequality] Let [math]\displaystyle{ G = (V,E) }[/math] be a connected unweighted graph, show that

[math]\displaystyle{ \forall s,t,w\in V, R_{\mathrm{eff}}(s,t)\le R_{\mathrm{eff}}(s,w) + R_{\mathrm{eff}}(w,t). }[/math]

Problem 7 (Expander mixing lemma)

• Let [math]\displaystyle{ G }[/math] be a [math]\displaystyle{ d }[/math]-regular graph with spectral radius [math]\displaystyle{ \alpha:= \max\{\alpha_2, |\alpha_n|\} }[/math], show that
  1. the size of the maximum independent set is at most [math]\displaystyle{ \alpha n/d }[/math], and
  2. the chromatic number is at least [math]\displaystyle{ d/\alpha }[/math].

• Let [math]\displaystyle{ G }[/math] be a [math]\displaystyle{ d }[/math]-regular graph with spectral radius [math]\displaystyle{ \alpha:= \max\{\alpha_2, |\alpha_n|\} }[/math]. Design an approximation algorithm for the maximum cut problem: given [math]\displaystyle{ G }[/math], returns a set [math]\displaystyle{ T }[/math] such that

[math]\displaystyle{ |E(T, \overline T)| \ge (1 - 4 \alpha/d)\max_{S}|E(S, \overline S)| }[/math]

Problem 8 (MCMC and coupling)

In this problem, you will analyze the MCMC sampler over independent sets of a fixed size [math]\displaystyle{ k }[/math]. Given a graph [math]\displaystyle{ G=(V,E) }[/math] with maximum degree [math]\displaystyle{ \Delta }[/math], let [math]\displaystyle{ I_k }[/math] be the set of all independent sets in [math]\displaystyle{ G }[/math] of size [math]\displaystyle{ k }[/math]. Consider a random walk [math]\displaystyle{ \{X_i\}_{i\geq 0} }[/math] on [math]\displaystyle{ I_k }[/math] defined by the following process:

• choose a vertex [math]\displaystyle{ v\in X_t }[/math] uniformly at random and a vertex [math]\displaystyle{ w\in V }[/math] uniformly at random;

• if [math]\displaystyle{ w\notin X_t }[/math] and [math]\displaystyle{ X_t - \{v\} + \{w\} }[/math] is independent, [math]\displaystyle{ X_{t+1} = X_t - \{v\} + \{w\} }[/math];

• otherwise, [math]\displaystyle{ X_{t+1} = X_t }[/math].

Use coupling argument to show that if [math]\displaystyle{ k\leq \frac{n}{3\Delta + 3} }[/math], then the [math]\displaystyle{ \epsilon }[/math]-mixing time of [math]\displaystyle{ \{X_i\}_{(i\geq 0)} }[/math] is a polynomial in [math]\displaystyle{ n }[/math] and [math]\displaystyle{ \log(1/\epsilon) }[/math].