高级算法 (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].

• [Coloring 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 points] Let [math]\displaystyle{ G }[/math] be a connected graph, and [math]\displaystyle{ \lambda_1\le \lambda_2 \le \ldots \le \lambda_n }[/math] be the eigenvalues of its normalized Laplacian matrix [math]\displaystyle{ \mathcal{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] 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 1/O(rn) \geq 1/O(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 d/O(n^2) }[/math].

Problem 8 (MCMC and coupling)

In this problem, you will analyze the MCMC sampler over independent sets of fixed size. Given 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]

(1) Show that the Markov chain [math]\displaystyle{ \{X_i\}_{i\geq 0} }[/math] is irreducible and aperiodic.

(2) Show that the stationary distribution of [math]\displaystyle{ \{X_i\}_{i\geq 0} }[/math] is the uniform distribution over [math]\displaystyle{ I_k }[/math].

(3) 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].