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

  • $\begingroup$ Just a random thought - can the Lovasz Local Lemma be useful? $\endgroup$
    – Seva
    Jul 31 '11 at 20:34
  • 1
    $\begingroup$ @Seva: 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})$ $\endgroup$ Jul 31 '11 at 20:57
  • 3
    $\begingroup$ I would try the second moment method. Does that not work? $\endgroup$ Jul 31 '11 at 23:29
  • 1
    $\begingroup$ @ 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. $\endgroup$ Aug 3 '11 at 19:16
  • 5
    $\begingroup$ Dear Matt, If you solved your own question perhaps you should add the answer as either an answer or as part of the question. $\endgroup$
    – Gil Kalai
    Nov 27 '12 at 10:36

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.