Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Qiaochu Yuan Oct 5 '12 at 1:32
    
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. –  Qiaochu Yuan Oct 5 '12 at 1:35
    
@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$. –  natema Oct 5 '12 at 18:26
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 :-). –  joriki Oct 14 '12 at 9:43
    
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. –  joriki Oct 14 '12 at 9:48
show 3 more comments

1 Answer

up vote 2 down vote accepted

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)\;. $$

share|improve this answer
add comment

Your Answer

 
discard

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.