Consider the graph G = (V,E) on n vertices which is generated by the following random process: for each pair of vertices u and v, we flip a fair coin and place an (undirected) edge between u and v if and only if the coin comes up heads.

(a) What is the size of the sample space?

(b) A k-clique in graph is a set S of k vertices which are pairwise adjacent (every pair of vertices is connected by an edge). For example a 3-clique is a triangle. Let's call the event that S forms a clique ES. What is the probability of ES for a particular set S of k vertices?

(c) Suppose that V1 = {v1,...,vl} and V2 = {w1,...,wk} are two arbitrary sets of vertices. What conditions must V1 and V2 satisfy in order for EV1 and EV2 to be independent? Prove your answer.

(d) Prove that n nk. (You might find this useful in part (e)) k

(e) Prove that the probability that the graph contains a k-clique, for k 4log2 n + 1, is at most 1/n.