Number of $K_4$ in $G(n, \sqrt{n})$

58 Views Asked by At

What can you say about the number of copies of $K_4$ in $G(n, \sqrt{\frac{1}{n}})$? What is the asymptotic probability that it is greater than $n$?

Let me recall the binomial random graph model here. In the $G(n, p)$ model, a graph is constructed by connecting nodes randomly. Each edge is included in the graph with probability $p$ independent of every other edge. Equivalently, all graphs with $n$ nodes and $M$ edges have equal probability of $${\displaystyle p^{M}(1-p)^{{n \choose 2}-M}.}$$

My idea is:

Let $X$ be the number of copies of $K_4$ in $G(n, \sqrt{\frac{1}{n}})$. Then $E(X) = \binom{n}{4}{\sqrt{\frac{1}{n}}}^6$ and $$\operatorname{var}(X)= \binom{n}{4}{\sqrt{\frac{1}{n}}}^6(1-{\sqrt{\frac{1}{n}}}^6)+ \binom{n}{6}\binom{6}{2,2,2}({\sqrt{\frac{1}{n}}}^{11}-{\sqrt{\frac{1}{n}}}^{12})+ \binom{n}{5}\binom{5}{3,1,1}({\sqrt{\frac{1}{n}}}^9-{\sqrt{\frac{1}{n}}}^{12}).$$ I think in the next step we should estimate the number of copies of $K_4$ by Chebyshev’s Inequality. For the second case, the threshold for containing $K_4$ in $G(n,p)$ is $n^{-\frac{2}{3}}$, and $n^{-\frac{2}{3}} \ll n^{-\frac{1}{2}}$, so we have at least one $K_4$ in $G(n, \sqrt{\frac{1}{n}})$ with high probability. Also, from the above computation we can see $\frac{\operatorname{var}(X)}{E^2(X)}\to 0$ as $n\to\infty$, therefore $$P(1\leq X < 2E(X))\to 1\,\,\text{as}\, n\to\infty$$