5 Cliques in Random Graphs 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 kclique in graph is a set S of 1: vertices which are pairwise adjacent (every pair of vertices is connected by an edge). For example a 3-c1ique is a triangle. Let's call the event that S forms a clique 83. What is the probability of E 3 for a particular set S of k vertices? (c) Suppose that V] = {V},. . .,Vg} and V2 = {w1,...,wk} are two arbitrary sets of vertices. What conditions must V1 and V2 satisfy in order for Ev. and ili'v2 to be independent? Prove your answer. (d) Prove that (E) 5 :1". (You might nd this useful in part (e)) (e) Prove that the probability that the graph contains a kclique, for k 2 410g; :1 + l, is at most 1