In an Erdős–Rényi random graph, what is the threshold for the property "every edge is contained in at least one triangle"?

Question

Let $G(n,p)$ denote the Erdős–Rényi random graph, where $n$ is the number of nodes and $p$ is the probability for each edge. I'm interested in precisely what range of $p$ the random graph has at least one edge not contained in any triangle.

One easily checks that if $$p \ge \left( \frac{2 \log n + \omega}{n} \right)^{1/2}, $$ where $\omega \to \infty$ arbitrarily slowly, then every pair of vertices is a.a.s. connected by a path of length $2$, so it follows that every edge is contained in a triangle.

This can be sharpened though. Let $X$ denote the expected number of edges not in any triangle.

Then $$E[X] = {n \choose 2} p (1-p^2)^{n-2},$$ and if I did my calculation correctly, then if $$p \ge \left( \frac{(3/2) \log n + (1/2) \log \log {n} + \omega}{n} \right)^{1/2}$$ then there are a.a.s. no edges not contained in any triangles, since $E[X] \to 0$ as $n \to \infty$.

My guess is that this inequality is more-or-less sharp. What I'd like to show then is that if $p$ is much smaller, then there are a.a.s. edges not contained in any triangle.

Suppose for example that $$p \ge \left( \frac{(3/2) \log n - C \log\log{n} }{n} \right)^{1/2}.$$ Is it true that for large enough constant $C>0$ we have a.a.s. that at least one edge not contained in any triangle? The expected number of such edges is tending to infinity as a power of $\log{n}$, but obviously that's not enough.

I have tried using Janson's inequality, for example, but I am stuck because the events I am trying to count are not pairwise independent even though they are "almost independent."

Answer 1

I just stumbled across this question and see that it is five years old, but since I know the reference I thought I might as well share it. This threshold is determined in the paper "Local Connectivity of a Random Graph" by Erdos, Palmer, and Robinson (JGT Vol 7 1983 pp. 411-417) -- see Theorem 2 and discussion preceding it.

Answer 2

Let $G$ be a random graph on $n$ vertices where each edge exists independently with probability $p = \frac{c}{n}$ for $c > 1$. The total number of edges in a complete graph on $n$ vertices is $m = {n \choose 2}$. For each edge $i$, define a random indicator variable: $$X_i = \begin{cases} 1 & \text{if edge } i \text{ is not contained in any triangle} \\ 0 & \text{otherwise} \end{cases}$$

Then we have $$E[X_i] = p(1-p^2)^{n-2} = \frac{c}{n} \left(1 - \left(\frac{c}{n}\right)^2\right)^{n-2}$$

The total expected number of edges not in any triangle is: $$\mu = \sum_{i=1}^{m} E[X_i] = m \cdot E[X_i] = {n \choose 2} \frac{c}{n} \left(1 - \left(\frac{c}{n}\right)^2\right)^{n-2}$$

To apply Janson's Inequality, we need to bound the dependency term Δ, which captures the influence of dependencies between events (edges being isolated): $$\Delta = \sum_{i \neq j} E[X_iX_j]$$

We can split this into two cases:

1. For edges $i$ and $j$ sharing a vertex, There are at most $O(n^3)$ such pairs. The probability of both edges being isolated, knowing they share a vertex, is at most: $$E[X_i X_j] \leq p^2(1-p^2)^{2(n-2)}$$

This leads to a contribution of $$O(n^3 p^2 (1-p^2)^{2(n-2)})$$ to $\Delta$.

2. If edges $i$ and $j$ share no vertices, we would actually never encounter this case since we're only considering pairs that have a direct dependency, which necessarily involves sharing vertices. Even if indirect dependencies might exist, they weaken quickly and become negligible in our analysis.

With $p = c/n$, as $n$ grows larger, $μ$ scales up considerably. Also $\Delta$ (dominated by Case 1) is suppressed due to the exponential decay in the terms and the polynomial factor.

Thus $\Delta = o(\mu^2)$, a condition for Janson's Inequality.

Janson's Inequality gives us the bound on the probability that none of the edges are isolated (i.e., every edge is in at least one triangle): $$P\left(\bigcap_{i} \{X_i = 0\}\right) \leq \exp\left(-\frac{\mu^2}{2(\mu + \Delta)}\right)$$

The left-hand side is the probability that all edges are involved in at least one triangle. As n increases, the right-hand side tends to 0.

This means that $$\lim_{n \to \infty} P[\text{all edges are contained in at least one triangle}] = 0$$

So almost surely, the graph will not be entirely composed of triangles. This implies an almost certain existence of at least one edge not contained within any triangle. Note that the behavior of $(1-p^2)^{n-2}$ is sensitive to how $p = \frac{c}{n}$ scales with $n$. For large $n$, the term inside the parentheses approaches 1 for any fixed $c$, but the rate of this approach and its impact on $\mu$ and $\Delta$ can vary.