Show With High Probability, No Vertex Belongs to More than One Triangle

Question

I am working on a random graphs problem, which is stated as follows:

Suppose that $p = d/n$, where $d$ is constant. Prove that with high probability (w.h.p.), no vertex belongs to more than one triangle.

For each $i \in \left[\binom{n}{3}\right] \cup \{0\}$, I define $X_{i}$ as the set of vertices in the graph that belong to $i$ triangles. I believe that I want to show that $Pr[v \in X_{0} \cup X_{1}] \to 1$ as $n \to \infty$.

I begin by fixing a vertex $v$ and deriving $Pr[v \in X_{0}]$ and $Pr[v \in X_{1}]$. If $v$ belongs to no triangles, it may have up to $n-1$ neighbors. If $v$ has at least two neighbors, none of them may be adjacent. This yields the probability:

$$Pr[v \in X_{0}] = (1-p)^{n-1} + (n-1)p(1-p)^{n-2} + \sum_{i=2}^{n-1} \binom{n-1}{i} p^{i} (1-p)^{n-i-1+\binom{i}{2}}$$

Similarly, if $v \in X_{1}$, it necessarily has at least two neighbors, and exactly two of its neighbors are adjacent. This yields the probability:

$$Pr[v \in X_{1}] = \sum_{i=2}^{n-1} \binom{n-1}{i} \binom{i}{2} p^{i+1} (1-p)^{n-i-2+\binom{i}{2}}$$

Am I correct that I want to show $Pr[v \in X_{0} \cup X_{1}] \to 1$ as $n \to \infty$? Would it be possible to get a nudge in the right direction on how to show the desired result (w.h.p., no vertex belongs to more than one triangle)?

I greatly appreciate everyone's time and effort to help me!

Answer 1

I think I have an answer. I would love some feedback or critiques of ways I could improve this (especially if I'm off base).

Define $X_{i}$ as above. We have:

$$Pr[v \in \bigcup_{i=2}^{\binom{n}{3}} X_{i}] = 1 - Pr[v \in X_{0}] - Pr[v \in X_{1}]$$

It suffices to show:

$$\lim_{n \to \infty} Pr[v \in \bigcup_{i=2}^{\binom{n}{3}} X_{i}] = \lim_{n \to \infty} (1 - Pr[v \in X_{0}] - Pr[v \in X_{1}]) = 0$$

We have: $Pr[v \in X_{0}]$ and $Pr[v \in X_{1}]$ as in the OP. Evaluating $Pr[v_{0} \in X_{1}] + Pr[v \in X_{1}]$:

$$Pr[v_{0} \in X_{1}] + Pr[v \in X_{1}] = (1-p)^{n-1} + (n-1)p(1-p)^{n-2} + \sum_{k=2}^{n-1} \binom{n-1}{k}p^{k}(1-p)^{n-k-2+\binom{k}{2}} \biggr[ \biggr( \binom{k}{2} - 1 \biggr)p + 1 \biggr]$$

Evaluating: $$ \lim_{n \to \infty} Pr[v_{0} \in X_{1}] + Pr[v \in X_{1}] = \lim_{n \to \infty} (1-p)^{n-1} + \lim_{n \to \infty} (n-1)p(1-p)^{n-2} + \lim_{n \to \infty} \sum_{k=2}^{n-1} \binom{n-1}{k}p^{k}(1-p)^{n-k-2+\binom{k}{2}} \biggr[ \biggr( \binom{k}{2} - 1 \biggr)p + 1 \biggr] $$

We have $\lim_{n \to \infty} (1-p)^{n-1} + \lim_{n \to \infty} (n-1)p(1-p)^{n-2} = e^{-d}(1 + d)$.

Now applying the linearity property of the limit, we obtain:

$$\lim_{n \to \infty} \sum_{k=2}^{n-1} \binom{n-1}{k}p^{k}(1-p)^{n-k-2+\binom{k}{2}} \biggr[ \biggr( \binom{k}{2} - 1 \biggr)p + 1 \biggr] = $$

$$\sum_{k=2}^{\infty} \lim_{n \to \infty}\binom{n-1}{k}p^{k}(1-p)^{n-k-2+\binom{k}{2}} \biggr[ \biggr( \binom{k}{2} - 1 \biggr)p + 1 \biggr]$$

Distributing $\biggr[ \biggr( \binom{k}{2} - 1 \biggr)p + 1 \biggr]$ and applying the linearity property of the limit again, we obtain:

$\lim_{n \to \infty}\binom{n-1}{k}p^{k+1}(1-p)^{n-k-2+\binom{k}{2}} (\binom{k}{2}-1) = 0$.

So:

$$\sum_{k=2}^{\infty} \lim_{n \to \infty}\binom{n-1}{k}p^{k}(1-p)^{n-k-2+\binom{k}{2}} \biggr[ \biggr( \binom{k}{2} - 1 \biggr)p + 1 \biggr] = $$

$$\sum_{k=2}^{\infty} \lim_{n \to \infty}\binom{n-1}{k}p^{k}(1-p)^{n-k-2+\binom{k}{2}}$$

And $\lim_{n \to \infty}\binom{n-1}{k}p^{k}(1-p)^{n-k-2+\binom{k}{2}} = \dfrac{d^{k}}{e^{d}k!}$.

Thus:

$$\sum_{k=2}^{\infty} \lim_{n \to \infty}\binom{n-1}{k}p^{k}(1-p)^{n-k-2+\binom{k}{2}} = \sum_{k=2}^{\infty} \dfrac{d^{k}}{e^{d} k!} = \dfrac{e^{d} - d - 1}{e^{d}}$$

Recall $\lim_{n \to \infty} (1-p)^{n-1} + \lim_{n \to \infty} (n-1)p(1-p)^{n-2} = e^{-d}(1 + d)$. Adding these limits up yields: $1$.

And so: $\lim_{n \to \infty} (1 - Pr[v \in X_{0}] - Pr[v \in X_{1}]) = 0$, proving the desired result.

Answer 2

There is a simple argument showing that asymptotically no vertex is involved is more than one triangle.

Let $g$ be a subgraph containing at least two triangles, $k$ its number of vertices, $m$ its number of edges. This is subgraph of excess at least 1 (i.e. $m-k \geqslant 1$). Now what is the probability to find $g$ in a graph where all edges are independently taken with probability $c \cdot n^{-1}$? There are ${n \choose k}=\Theta(n^k)$ ways to find such a subset of vertices. Each subset has at least $m$ edges with probability $\Theta(n^{-m})$. So overall the probability to find $g$ is $\Theta(n^{k-m})= O(n^{-1})$, so is vanishing.