Fall 2011 Homework 8: Question 7
A network consists of n nodes, each pair of which may or may not have an edge joining them. For example, a social network can be modeled as a group of n nodes (representing people), where an edge between i and j means they know each other. Assume the network is undirected and does not have edges from a node to itself (for a social network, this says that if i knows j, then j knows i and that, contrary to Socrates' advice, a person does not know himself or herself). A clique of size k is a set of k nodes where every node has an edge to every other node (i.e., within the clique, everyone knows everyone). An anticlique of size k is a set of k nodes where there are no edges between them (i.e., within the anticlique, no one knows anyone else). For example, the picture below shows a network with nodes labeled 1, 2,..., 7, where {1, 2, 3, 4} is a clique of size 4, and {3, 5, 7} is an anticlique of size 3.
(a) Form a random network with n nodes by independently flipping fair coins to decide for each pair {x, y} whether there is an edge joining them. Find the expected number of cliques of size k (in terms of n and k).
(b) A triangle is a clique of size 3. For a random network as in (a), find the variance of the number of triangles (in terms of n). Hint: find the covariances of the indicator random variables for each possible clique. There are nC3 such indicator r.v.s, some pairs of which are independent and other pairs which are independent.
(c) Suppose that $\binom{n}{k}<2^{\binom{k}{2}-1}$. Show that there is a network with n nodes containing no cliques of size k or anticliques of size k. Hint: explain why it is enough to show that for a random network with n nodes, the probability of the desired property is positive; then consider the complement.
Solution: Consult iTunes course for full solution.
"Mathematics is the logic of certainty, but statistics is the logic of uncertainty."