1
$\begingroup$

I am looking at the random graph model $G(n,p)$ (i.e., the random graph on $n$ vertices where each edge appears independently with probability $p$).

A property of almost every graph is a property $A$ such that $\lim_{n \to \infty} \mathbb{P}(G(n,p)\text{ has } A) = 1$.

The question I wish to solve is the following: is it the case that for almost every graph, every vertex is contained in a triangle?

My attempt: I suspect that this is a property of almost every graph, because $G(n,p)$ has $\binom{n}{2}p \sim n^2p$ edges on average, which is much more than the number of edges you would need to have every vertex be in a triangle $(\leq 3n)$. It would suffice to prove the probability that some vertex is not in a triangle goes to zero. Call such a vertex a bad vertex. We have \begin{align*} \mathbb{P}(\text{there exists a bad vertex}) &\leq \mathbb{E}[\text{number of bad vertices}]\\ &= \sum_{v} \mathbb{P}(v \text{ is a bad vertex})\\ &= n \mathbb{P}(v\text{ is a bad vertex}). \end{align*} So I would need an upper bound on $\mathbb{P}(v\text{ is a bad vertex})$ that is $o(1/n$). So far I've been unable to come up with a useful bound. Any advice would be appreciated.

$\endgroup$
2
$\begingroup$

A given vertex is a member of ${n-1 \choose 2} \sim \frac 12n^2$ possible triangles. Each of them is realized with probability $p^3$ and the probabilities are (reasonably) independent, so the chance a vertex is bad is of order $(1-p^3)^{(\frac 12n^2)}$. The expected number of bad vertices is then $n(1-p^3)^{(\frac 12n^2)}$, which duly goes to $0$ as $n \to \infty$

If the failure of independence bothers you, partition the $n$ vertices other than the one we are considering into disjoint pairs and only consider triangles of one pair plus the vertex we are looking at. That certainly reduces the chance that we know our vertex is good, but changing the exponent to $\frac n2$ still supports the desired conclusion. For fixed $p$ almost every graph has every vertex in a triangle.

$\endgroup$
  • 1
    $\begingroup$ Thank you! I started down that pathway but got stuck on the triangles not actually being independent. $\endgroup$ – kccu Jan 22 at 21:37
  • $\begingroup$ Instead of handwaving with "reasonable independence", we can certainly say that each vertex is part of an expected number of $p^3{n-1\choose 2}$ triangles. I guess one could similarly find the variance and then use chebyshev ... $\endgroup$ – Hagen von Eitzen Jan 22 at 21:39
  • $\begingroup$ @HagenvonEitzen: that is why I added the second paragraph. It assures independence and gets us there. $\endgroup$ – Ross Millikan Jan 22 at 21:44
  • $\begingroup$ Alternatively, we could separately argue that, for example (1) every vertex has at least $\frac n3$ neighbors w.h.p., and (2) there is no independent set of size $\frac n3$ w.h.p. $\endgroup$ – Misha Lavrov Jan 23 at 0:13

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .