Problem 2. (10 pts) Lower bound on Ramsey numbers A clique on k nodes is the complete graph on these n nodes: between any two nodes there's an edge. Thus, a clique on k nodes has ) edges (a) (2 pts) Suppose we color the edges of a clique on k nodes randomly, independently and uniformly in red or blue. Show that the probability that the clique is monochromatic - namely, all edges are colored by the same color _is 22 (b) (1 pts) Argue by induction that for any k > 3 we have 2 1. c) (7 pts) Suppose we color the edges of a clique on n nodes randomly, independently and uniformly in red or blue. Show that the expected number of monochromatic cliques of size k we create is strictly smaller than 1 given that k 2 2log(n) 2 3. Hint: Make sure you define the suitable Bernoulli random variables. You may also use the nave bound: n (n-1 k! Explanation: The Ramsey number R(k, l) is the smallest natural n such that any coloring of the edges of the complete graph over n nodes in red or blue must produce either a monochromatic red clique of size k or a monochromatic blue clique of size l. We argue that you have just proven that R(k, k) > 2