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).

(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 . 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.*

(c) Suppose that . Show that there is a network with n nodes containing no cliques of size k or anticliques of size k.

Solution:
Consult iTunes course for full solution.

Copyright © 2011 Stat 110 Harvard.
Website layout by former Stat110'er.