MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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

This should be a comment, but I don't quite have the reputation to do that yet. (sorry!)

In response to 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})$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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