Question 3

Hi, could anyone provide any assistance on this? I have a feeling there's going to be a question like this on the exam and I really have no idea how to approach this concept. Any help on either part would be appreciated.


Let $X_{ijkl}$ denote the indicator random variable that with (randomly) selected nodes $i,j,k,l$ there is a 4-clique ($K_4$) in the ER random graph $G(n,p)$, i.e.,

$ X_{ijkl} = \begin{cases} 1, & \text{if there is a } K_4 \text{ on } i,j,k,l \\ 0, & \text{otherwise} \end{cases} $

  • Then we have $E[X_{ijkl}]=P(X_{ijkl}=1)=p^6$ (since there are ${4}\choose{2}$ $=6$ edges on a $K_4$ and they are independently drawn with probability $p$).

  • Now, $E[\text{number of } K_4 \text{ in G}]$

    $= E\left[\sum\limits_{\{i,j,k,l\}}X_{ijkl}\right]=\sum\limits_{\{i,j,k,l\}}E[X_{ijkl}] \text{ }$ (by linearity of expectation)

    $={{n}\choose{4}}p^6 \approx n^4p^6 = (n^{2/3}p)^6$

  • Hence, by Markov inequality, we have,

    $P(\text{number of } K_4 \geq 1) \leq \frac{E[\text{number of } K_4]}{1} \approx (n^{2/3}p)^6 \to 0$ as $n \to \infty$.

  • Hence $P(G \text{ contains a } K_4) \to 0$ as $n \to \infty$.

  • $\begingroup$ Wow thanks, it makes a lot of sense when you say it like that. $\endgroup$ – A. Boy Apr 11 at 22:22
  • $\begingroup$ Actually, sorry I am still confused, how does (𝑛2/3𝑝)6 approach 0 as n approaches infinite? Shouldn't it approach infinite? $\endgroup$ – A. Boy Apr 11 at 22:41
  • $\begingroup$ $\lim\limits_{n\to \infty} \frac{p}{n^{-2/3}}\to 0$ since $p=o(n^{-2/3})$, by definition of $o(.)$ $\endgroup$ – Sandipan Dey Apr 11 at 22:50
  • $\begingroup$ Yup, forgot that part was in the original question, thanks $\endgroup$ – A. Boy Apr 12 at 0:11

First we find the probability that any set of 4 vertices is $K_4$. We say each potential edge can either be an edge in the graph (marked 1), or not (marked 0). We are given given $\mathbb P(edge=1) = p$ for all edges.

Note for any set of 4 vertices, since there are $\binom{4}{2}$ edges. $P(K_4 \text{ given 4 vertices}) = P(\text{all edges between the 4 vertices are set to 1 }) = p^{\text{no of edges}}$

Therefore, $P(K_4 \text{ given 4 vertices}) = p^{\binom{4}{2}} = p^6$.

Now \begin{align*} \mathbb E[\text{number of $K_4$ subgraphs}] &= \text{ways to choose 4 vertices}\cdot P(K_4 \text{ given 4 vertices})\\ &= \binom{n}{4}p^6 \end{align*}

Note that, $\lim\limits_{n\to\infty}\binom{n}{4}p^6 \simeq \lim\limits_{n\to\infty}(n^{\frac{2}{3}}p)^6\to0$

  • $\begingroup$ Could you explain how that limit approaches zero? It looks like it should approach infinite $\endgroup$ – A. Boy Apr 11 at 22:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.