[Math] Expected number of m-cliques in a random graph

graph theoryprobabilityrandom-graphs

Let $Z_m$ be a random variable that corresponds to the number of $m$-cliques in a random graph with n vertices and the probability of any edge happening is 1/2. Prove that $$ \mbox{E}[Z_m] = {n \choose m} 2^{-{m \choose 2}}.$$

Best Answer

What is an $m-$clique?

An $m$-clique is a set of $m$ vertices such that every two distinct vertices are adjacent.   IE: There is an edge connecting ever pair of vertices in the set.

How many $m$-cliques could there be?

The number of plausible $m$-cliques in a random graph of $n$ vertices, is the count of selections for $m$ from $n$ vertices.

What is the probability that a particular $m$-clique happens.

The probability that a particular set of $m$ vertices actually form an $m$-clique is the probability that every edge joining any two of those points are connected. How many such edges are there ? What is the probability that all these connections happen?

Put it together using the Linearity of Expectation.

You can do it, if you try.

Related Question