Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Assignment 5
1. (20 points) Recall the definition of Graph Laplacian (for undirected Graph). The main property of the graph Laplacian is that
We will use the above observation to show the following two claims.
(a) (10 points) Show that if the graph is not connected, then the 2nd eigenvalue of the Laplacian Matrix is 0.
(b) (10 points) Show that if the the 2nd eigenvalue of the Laplacian Matrix is 0, the graph is not connected.
2. (30 points) Suppose we pick m-many n-dimensional vectors, v1, . . . , vm ∈ Rn. Each coordinate is +1 with probability 1/2 and −1 with probability 1/2 and are chosen i.i.d. at random.
(a) (10 points) For fixed i, j ∈ [m] with i ≠ j, upper bound the probability of |⟨vi, vj⟩| ≤ α√n.
(b) (10 points) Using Union Bound, show that with probability 1 − o(1), every pair |⟨vi, vj⟩| ≤ α√n where α = 100 logm.
(c) (10 points) Use the previous part to show that with probability 1 − o(1), if points are chosen uniformly at random, all pairs of points are far apart. That is
for the same parameter α = 100 logm.