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

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

• Just a random thought - can the Lovasz Local Lemma be useful? – Seva Jul 31 '11 at 20:34
• I would try the second moment method. Does that not work? – Douglas Zare Jul 31 '11 at 23:29
• @ Douglas Zare: Yes, in the end the second moment does work. That was the first thing I tried, but I was making a mistake and didn't think it worked. Thanks, your comment got me to try the calculation again. – Matthew Kahle Aug 3 '11 at 19:16
• Dear Matt, If you solved your own question perhaps you should add the answer as either an answer or as part of the question. – Gil Kalai Nov 27 '12 at 10:36

Using the Local Lemma directly on the event $A_e$ = "the edge $e$ is not a part of a triangle" directly won't improve on the union bound, because for any edges $e_1 = (a,b)$ and $e_2 = (c,d)$, $A_{e_1}$ and $A_{e_2}$ are dependent -- if $e_1$ is not in a triangle, then we know that out of the two possible triangles $(c,d,a)$ and $(c,d,b)$, at most one can exist, removing one possible triangle $e_2$ can be in, and hence slightly increasing $P(A_{e_2})$