How can I compute the threshold probabilities at which different subgraphs appear in a random graph?

Question

I am very new to graph theory and I am stuck on the concept of thresholds for the Erdos-Renyi random model. In particular, I would like to calculate the threshold for the appearance of triangles and the threshold for the appearance of components having three edges. I know the first one is 1/n because I read it everywhere on the internet. I cannot find any clear explanation for that result. I don’t know whether I should use Markov inequality or Chebyshev, or neither of them. Sorry to bother here, but I am very confused.

Answer 1

There are two steps: showing that the threshold is not too low, and showing that it is not too high.

When $p$ is below the threshold

If we think that the threshold for triangles is $\frac1n$, our first step should be to show that when $p \ll \frac1n$, then w.h.p. there are no triangles in $G_{n,p}$. This is done using Markov's inequality.

Let $X$ be the number of triangles in $G_{n,p}$. We can write $X$ as the sum of indicator variables $X_{\{i,j,k\}}$, where $X_{\{i,j,k\}}=1$ if vertices $i,j,k$ form a triangle and $X_{\{i,j,k\}}=0$ otherwise. Since $\Pr[X_{\{i,j,k\}}=1] = p^3$ (all three edges must be present), we have $\mathbb E[X_{\{i,j,k\}}] = p^3$ as well. There are $\binom n3$ choices of $\{i,j,k\}$, so $X$ is the sum of $\binom n3$ variables with expected value $p^3$. By linearity of expectation, $\mathbb E[X] = \binom n3 p^3$.

If $p \ll \frac1n$, then $n^3 p^3 \to 0$ as $n \to \infty$, so $\mathbb E[X] \to 0$ as $n \to \infty$, and therefore (by Markov's inequality) $\Pr[X \ge 1] \to 0$ as $n \to \infty$. This means that, with high probability, there are no triangles.

When $p$ is above the threshold

If $p \gg \frac1n$, then the same argument says that $\mathbb E[X] \to \infty$ as $n \to \infty$, which means that the average number of triangles is large - but that does not mean that the number of triangles is large on average. You could imagine a random variable $Y$ with $\Pr[Y=n^2] = \frac1n$ and $\Pr[Y=0] =1 - \frac1n$; then $\mathbb E[Y] \to \infty$ as $n \to \infty$ and yet $Y=0$ with high probability.

To work around this, we should use the second moment method. Its simplest form is the inequality $$\Pr[X \ne 0] \ge \frac{\mathbb E[X]^2}{\mathbb E[X^2]}.$$ (This is the Cauchy-Schwarz inequality with respect to the inner product $\langle X,Y\rangle = \mathbb E[XY]$, applied to $X$ and the random variable $Y$ which is $1$ when $X \ne 0$ and $0$ otherwise.) Chebyshev's equality would also work, and the calculations would be very similar.

We have already computed $\mathbb E[X]$ for triangles, so we know $\mathbb E[X]^2$. To compute $\mathbb E[X^2]$, square our previous sum: $$ X^2 = \left(\sum_{\text{triples }\{i,j,k\}} X_{\{i,j,k\}}\right)^2 = \sum_{\text{triples }\{a,b,c\}} \sum_{\text{triples }\{d,e,f\}} X_{\{a,b,c\}} X_{\{d,e,f\}}. $$ We can replace $X_{\{a,b,c\}} X_{\{d,e,f\}}$ by $\mathbb E[X_{\{a,b,c\}} X_{\{d,e,f\}}]$ to find $\mathbb E[X^2]$.

By far the largest contribution to this sum comes from terms $\mathbb E[X_{\{a,b,c\}} X_{\{d,e,f\}}]$ where $\{a,b,c\} \cap \{d,e,f\} = \varnothing$. There are $\binom n3 \binom{n-3}{3}$ such terms, and $\mathbb E[X_{\{a,b,c\}} X_{\{d,e,f\}}] = p^6$, so we get $\binom n3 \binom{n-3}{3} p^6 = (1- o(1)) \binom n3^2 p^6 = (1- o(1)) \mathbb E[X]^2$.

When $p \gg \frac1n$, other terms contribute much less:

• When $|\{a,b,c\} \cap \{d,e,f\}| = 1$, there are only $O(n^5)$ such pairs of triples, but they still have a probability of $p^6$ of occurring: the two triangles form a butterfly graph with $6$ edges. So the total contribution is $O(n^5 p^6) = o(\mathbb E[X^2])$.
• When $|\{a,b,c\} \cap \{d,e,f\}| = 2$, there are $O(n^4)$ such pairs of triples and they have a probability of $p^5$ of occurring: the two triangles form a diamond graph with $5$ edges. So the total contribution is $O(n^4 p^5) = o(\mathbb E[X^2])$ (because $np \to \infty$).
• When $|\{a,b,c\} \cap \{d,e,f\}| = 3$ or in other words $\{a,b,c\} = \{d,e,f\}$, there are $\binom n3$ such pairs of triples and they have a probability of $p^3$ of occurring, so the total contribution is $O(n^3 p^3) = o(\mathbb E[X^2])$.

This tells us that $$\Pr[X \ne 0] \ge \frac{\binom n3^2 p^6}{\binom n3 \binom{n-3}{3} p^6 + o(n^6p^6)} = 1 - o(1)$$ and therefore $X \ne 0$ with high probability.

Other cases

The key to applying this method to thresholds for subgraphs is thinking about ways that two copies of the subgraph can intersect. In the case of triangles, the intersections all ended up being less frequent than the cases with two disjoint triangles. Applying the second moment method doesn't work (and the threshold we get from the first moment method might not even be correct) in cases where some intersections appear more frequently than that.

This tends to happen if the graph we're looking at has a subgraph which is more dense than the original graph. For example, consider the $(4,1)$-lollipop graph. Here, the first moment method tells us that this graph does not appear when $p \ll n^{-5/7}$, but actually the copy of $K_4$ inside this graph is more limiting: the threshold for $K_4$ is $n^{-2/3}$, which is higher. For the lollipop graph, the second moment method would fail when we consider pairs of lollipops which share their copies of $K_4$.