Note that G is disconnected if and only if there is a set of vertices S CV that has an empty edge-boundary. Recall that the edge-boundary of a set vertices is defined as: as := {e = {x,y} E E: x E S, y & S}. These are the edges that are incident to one node in S and one node in V \S. First, we fix a specific set S CV and assume that |SI| k for some k E {1, 2, ..., N - 1}, in words we say that S has size k. Mathematically we could write S (), where () is the set of all subsets of V of size k. We want to estimate P(aS = 0). a. (Counting) Show that there are k(N k) possible edges connecting points in S to points in V \S. Since each edge is passed over independently with probability 1 p, we get the following upper-bound: (1) P(S = 0) = (1 p)k(NK). b. Draw the graph (in the sense of Calculus I) of the function f(x) = e-*. Then draw its tangent line approximation at x = 0. Finally, compute the second derivative f" and deduce that f is concave up. Hence, deduce that 1- x se for every value of x E R. Using part b., we can rewrite (1) like this (2) P(as = 0) N - 1 The term N/(N 1) is always greater than 1. The term (1-4/3)(1+E) is trickier. d. Show that (1 e) 3 3 (1-3) (1+e)k log N. (1-3) (1 +e) =1+ 1+ + Note that G is disconnected if and only if there is a set of vertices S CV that has an empty edge-boundary. Recall that the edge-boundary of a set vertices is defined as: as := {e = {x,y} E E: x E S, y & S}. These are the edges that are incident to one node in S and one node in V \S. First, we fix a specific set S CV and assume that |SI| k for some k E {1, 2, ..., N - 1}, in words we say that S has size k. Mathematically we could write S (), where () is the set of all subsets of V of size k. We want to estimate P(aS = 0). a. (Counting) Show that there are k(N k) possible edges connecting points in S to points in V \S. Since each edge is passed over independently with probability 1 p, we get the following upper-bound: (1) P(S = 0) = (1 p)k(NK). b. Draw the graph (in the sense of Calculus I) of the function f(x) = e-*. Then draw its tangent line approximation at x = 0. Finally, compute the second derivative f" and deduce that f is concave up. Hence, deduce that 1- x se for every value of x E R. Using part b., we can rewrite (1) like this (2) P(as = 0) N - 1 The term N/(N 1) is always greater than 1. The term (1-4/3)(1+E) is trickier. d. Show that (1 e) 3 3 (1-3) (1+e)k log N. (1-3) (1 +e) =1+ 1+ +