3
$\begingroup$

Given an Erdős-Rényi graph $G(n,p)$ (that is, a random graph where each edge exists with probability $p$), what is the probability of having a "triangle"?

Given $3$ nodes in the graph, the probability of having a triangle among them is $p^3$; in the worst case, none of the three edges among them had happen to realize; then, we can pick other three nodes (maybe choosing one of them from the three nodes previously picked) and see again if a triangle happen to be there; we can continue repeatedly picking three nodes with at most one of them in common with a previous picking, until this is possible. Then we have $j$ possibilities of see a triangle, where $j$ is the maximum number of triples of vertices such that any pair of triples shares at most one vertex. The problem to find $j$ was solved by Spencer's theorem (1968): $$ j=\begin{cases} \frac{n}{3}\frac{n-1}{2} & \text{if }n\not\equiv_{6}5\\ \frac{n}{3}\frac{n-1}{2}-1 & \text{if }n\equiv_{6}5 \end{cases}$$

Then a rough lower bound is $1-(1-p^3)^{n(n-1)/6-1}$.

Anyone with something better?

  • 0
    Is there any particular reason you aren't using $G(n, p)$? Even if you're ultimately only interested in the answer for $G(n, 1/n)$, it seems unnecessarily confusing to me to only think about this case; then you can't tell which $n$ contributes which parts of your formulas at a glance.2012-10-05
  • 0
    Also, the title and the body don't match; calculating the expected number of triangles is straightforward compared to calculating the probability that at least one triangle exists.2012-10-05
  • 0
    @QiaochuYuan yes, I don't know how it happened to me to write a totally unrelated question in the title. I'm interested in the case where each node has a constant (expected) degree, then I choose that $p$; I've edited it fixing the incoherence (I apologize to Douglas S. Stones that answered the question about expectation), and restating the question with general $p$.2012-10-05
  • 1
    You managed to misspell both of the names of those people :-) Note that in most languages that use diacritics, the letters with and without diacritics have only a historical connection and are pronounced quite differently nowadays. Thus leaving off the diacritics is about as bad a misspelling as changing the vowels completely; you might as well have written "Erdas-Runyi". If you can't produce letters with diacritics, you can always copy them from the Web, e.g. from the corresponding Wikipedia articles (which you can find by Googling the names without diacritics :-).2012-10-14
  • 0
    Note, by the way, that the expectation $\binom n3p^3$ that Douglas gave for the number of triangles is an upper bound for the probability that a triangle exists.2012-10-14
  • 0
    Also, your lower bound is wrong; it could easily be above $1$, which should be impossible. Your argument shows that we have $j$ independent chances to find a triangle, so the probability of finding one is at least $1-(1-p^3)^{n(n-1)/6-1}$.2012-10-14
  • 0
    @joriki, many thanks for all the remarks, I apologize again for my errors.2012-10-15
  • 0
    You're welcome.2012-10-15

1 Answers 1

2

The probability that there is at least one triangle can be expressed using inclusion/exclusion:

$$ \mathbb{P}\biggl(\bigcup_{i=1}^n A_i\biggr) =\sum_{k=1}^n (-1)^{k-1}\sum_{\scriptstyle I\subset\{1,\ldots,n\}\atop\scriptstyle|I|=k} \mathbb{P}\left(\bigcap_{i\in I} A_i\right)\;, $$

where the $A_i$ are the events of individual triangles existing. I don't see a way to evaluate this in closed form, but it can be used to expand the desired probability in powers of $p$, and truncating the sum at some $k$ yields successively improved bounds (upper bounds for odd $k$ and lower bounds for even $k$). In the asymptotic case of fixed $\lambda=np$ as $n\to\infty$, the series can be summed exactly and yields a probability of $1-\mathrm e^{-\lambda^3/6}$.

The $k=1$ term is just the expectation value that Douglas gave in his now-deleted answer, $\binom n3p^3$, which is an upper bound for the desired probability by the first moment method (which can be regarded as a special case of the present approach).

The term for $k=2$ triangles yields contributions with $5$ and $6$ edges. With $5$ edges, there are $\binom n4$ ways to select four vertices and $6$ ways to select one of the $6$ edges between them that isn't used, for a contribution of $6\binom n4p^5$. With $6$ edges, we can either have $5$ different vertices, with $5$ options to choose the shared vertex and $\frac12\binom42=3$ options to choose pairs among the remaining $4$, for a contribution of $15\binom n5p^6$, or we can have $6$ different vertices, with $\frac12\binom63=10$ options to choose triangles among them, for a contribution of $10\binom n6p^6$. Thus the desired probability $q$ is bounded by

$$ \binom n3p^3-\left(6\binom n4p^5+15\binom n5p^6+10\binom n6p^6\right)\le q\le\binom n3p^3\;. $$

Asymptotically, if you keep $\lambda=np$ constant as $n\to\infty$, this becomes

$$\frac{\lambda^3}6-\frac{\lambda^6}{72}\lesssim q\lesssim\frac{\lambda^3}6\;.$$

For $k$ edges, the only contribution with enough powers of $n$ to match the $k$ powers of $p$ is one where there is only one edge per vertex, namely where the $k$ edges form $k/3$ triangles among $k$ vertices. Thus, asymptotically, the desired probability is given by

$$ q\sim\sum_{j=1}^\infty(-1)^{j-1}\frac{\lambda^{3j}}{6^jj!}=1-\mathrm e^{-\lambda^3/6}\;. $$

In the original form of your question, in which you had $p=1/n$ and thus $\lambda=1$, this would be $1-\mathrm e^{-1/6}\approx0.1535$.

If you want the full finite-size expansion in powers of $p$ up to $6$-th order, you need to include the contribution $\binom n4p^6$ from all $6$ edges formed by $4$ vertices to get

$$ q = \binom n3p^3-\left(6\binom n4p^5+15\binom n5p^6+10\binom n6p^6+\binom n4p^6\right)+O\left(p^7\right)\;. $$