# Graph Theory - Binomial Random Graphs [closed]

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

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

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