高级算法 (Fall 2023)/Problem Set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Zouzongrui (talk | contribs)
No edit summary
Zouzongrui (talk | contribs)
No edit summary
Line 22: Line 22:


*['''Lowerbounding <math>\lambda_2</math>'''] Let <math>G</math> be an undirected graph whose Laplacian is <math>L</math>, with second-smallest eigenvalue <math>\lambda_2</math>.  We know that if <math>G</math> is connected then <math>\lambda_2>0</math>. Prove that <math>\lambda_2 \geq 1/O(rn) \geq  1/O(n^2)</math> by analyzing the Rayleigh quotient on all test vectors <math>x\perp \mathbf{1}</math>. Here, <math>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>G</math> is simple and <math>d</math>-regular, we have <math>\lambda_2 \geq d/O(n^2)</math>.
*['''Lowerbounding <math>\lambda_2</math>'''] Let <math>G</math> be an undirected graph whose Laplacian is <math>L</math>, with second-smallest eigenvalue <math>\lambda_2</math>.  We know that if <math>G</math> is connected then <math>\lambda_2>0</math>. Prove that <math>\lambda_2 \geq 1/O(rn) \geq  1/O(n^2)</math> by analyzing the Rayleigh quotient on all test vectors <math>x\perp \mathbf{1}</math>. Here, <math>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>G</math> is simple and <math>d</math>-regular, we have <math>\lambda_2 \geq d/O(n^2)</math>.
== Problem 3 (Cheeger's inequality) ==
== Problem 4 (Random walk on graph) ==
== Problem 5 (Hitting time, commute time) ==
== Problem 6 (Electrical network) ==
== Problem 7 (Expander mixing lemma) ==
== Problem 8 (MCMC and coupling) ==

Revision as of 07:33, 24 November 2023

  • 本次作业每个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].

Problem 3 (Cheeger's inequality)

Problem 4 (Random walk on graph)

Problem 5 (Hitting time, commute time)

Problem 6 (Electrical network)

Problem 7 (Expander mixing lemma)

Problem 8 (MCMC and coupling)