Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CMPSC497
Spring 2024
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.