Graph Theory - Binomial Random Graphs

Question

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.

Answer 1

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

Answer 2

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$