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

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

• 我们推荐大家使用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 (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] for any unit vector [math]\displaystyle{ x }[/math] and any PSD matrix [math]\displaystyle{ A }[/math].)

(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 4 (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].

Problem 5 (Cheeger’s Inequality)

Let [math]\displaystyle{ G=(V,E) }[/math] be a [math]\displaystyle{ d }[/math]-regular graph. Let [math]\displaystyle{ S, T, U }[/math] be a partition of the vertex set [math]\displaystyle{ V }[/math] with [math]\displaystyle{ |S| \le |T| }[/math] and [math]\displaystyle{ |U| \le \epsilon \cdot \min\{|S|,|T|\} }[/math]. We define the projected expansion by [math]\displaystyle{ \phi_G(S,T\|U) := \frac{E(S,T)}{d|S|} }[/math]. Let [math]\displaystyle{ \lambda_2 }[/math] be the second smallest eigenvalue of the normalized Laplacian [math]\displaystyle{ \mathcal{L} := (D-A)/d }[/math]. Show that there exists an efficient algorithm such that, for every [math]\displaystyle{ \epsilon \gt 0 }[/math], finds sets [math]\displaystyle{ S }[/math], [math]\displaystyle{ T }[/math], [math]\displaystyle{ U }[/math] such that [math]\displaystyle{ |S| \le |T| }[/math], [math]\displaystyle{ |U| \le \epsilon \min\{|S|,|T|\} }[/math], and [math]\displaystyle{ \phi_G(S,T\|U) \le O(\lambda_2 \cdot (1+ \frac{2}{\epsilon})) }[/math].

HINT: Try to modify the randomized thresholding in Cheeger's proof.