1
$\begingroup$

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}}.$$

$\endgroup$
3
  • 2
    $\begingroup$ How many possible m-cliques are there? What is the probability of a given m-clique being in a random graph? $\endgroup$
    – deinst
    Nov 10, 2016 at 1:58
  • $\begingroup$ Also, expectation is linear. $\endgroup$ Nov 10, 2016 at 2:08
  • $\begingroup$ The number of m-cliques is infinite since there are n vertices in this random graph. The probability of a given m-clique being in a random graph change from one m to another since different numbers of m requires different numbers of edges.@deinst $\endgroup$
    – user387795
    Nov 10, 2016 at 2:11

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you explain why is the probability part 2^{-(m choose 2)} $\endgroup$
    – user387795
    Nov 10, 2016 at 2:39
  • 1
    $\begingroup$ @dataKnight To form an $m$ clicue, how many edges need there be? What is the probability that all of them happen? $\endgroup$ Nov 10, 2016 at 2:52
2
$\begingroup$

I know this is an old problem, but I also faced the same doubt. Luckily, I was able to solve this doubt by myself. Hence, I provide how I solved it, so in case that anyone else is having the same doubt will find an easy to follow step-by-step proof of this result.

First of all, we need to understand that a clique of size $m$ is a set of m nodes, in which every node is connected to every other node (in a social network it would mean that everyone knows everyone else).

Hence in a network with $n$ nodes we choose all the subsets of size $m$. The total number of possible combinations (subsets) will be $\binom{n}{m}$.

Now we can define $\binom{n}{m}$ $X_j$ indicator r.v.s, i.e. $(X_1, X_2,...,X_\binom{n}{m}$), which indicate wheter the j subset is a clique or not.

Hence the Expected Number of cliques of size m will be the sum of those indicator r.v.s:

$E(X_1 + X_2 + ... + X_\binom{n}{m}) = E\left (\sum_{1}^{\binom{n}{m}} X_j \right )$

By symmetry of expectations we know that all those expectations are exactly the same. Hence, for example, we can multiply the Expectation of $X_1$ by $\binom{n}{m}$.

$E(X_1 + X_2 + ... + X_\binom{n}{m}) = E\left (\sum_{1}^{\binom{n}{m}} X_j \right ) = \binom{n}{m}E(X_1)$

Now by the fundamental bridge, we know that the expectation of an indicator r.v. is the same as its probability, i.e. $E(X_1) = P(X_1 = 1)$. In other words, we want to calculate the probability that the first subset of size m is a clique of size m.

To calculate this probability we only need to know the probability of any edge happening, which we will call $p$ (in this case it is $1/2$). Furthermore, we know that in order to form a clique all the nodes in this subset must be connected, that means that all possible combinations of 2 nodes from the $m$ subset, that is $\binom{m}{2}$. Hence:

$P(X_1 = 1) = (p)^\binom{m}{2} = (\frac{1}{2})^\binom{m}{2} = \frac{1}{2^\binom{m}{2}} = E(X_1)$

Putting all of this together, we obtain that:

$E(X_1 + X_2 + ... + X_\binom{n}{m}) = E\left (\sum_{1}^{\binom{n}{m}} X_j \right ) = \binom{n}{m}E(X_1) = \binom{n}{m}P(X_1 = 1) = \binom{n}{m} \frac{1}{2^\binom{m}{2}}$

So:

$E[Z_m]=\binom{n}{m} 2^{-\binom{m}{2}}$

where $Z_m = X_1 + X_2 + ... + X_\binom{n}{m}$

Hope this helps.

$\endgroup$

You must log in to answer this question.