18
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Just a random thought - can the Lovasz Local Lemma be useful? $\endgroup$
    – Seva
    Jul 31, 2011 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, 2011 at 20:57
  • 4
    $\begingroup$ I would try the second moment method. Does that not work? $\endgroup$ Jul 31, 2011 at 23:29
  • 2
    $\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, 2011 at 19:16
  • 6
    $\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, 2012 at 10:36

2 Answers 2

14
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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