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

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

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

• 我们推荐大家使用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].