# Probability of k triangles in a random graph

Let $G_{n,p}, n\in \mathbb{N}, p\in(0,1)$ be the binomial random graph, i.e. a graph on $n$ vertices where an edge is in $G_{n,p}$ with probability $p$ and denote as $V$ its vertex set.

Let $j\in \binom{V}{3}$ be a set of 3 vertices and denote as $\mathcal{E}_j$ the event that $j$ is a triangle. In terms of $p$, what is the the following probability?

$$\mathbb{P}\left(\bigcap_{j=1}^k \mathcal{E}_j\right),$$

i.e. the probability that $k$ such sets of 3 vertices are all triangles. I have trouble counting the cases where edges are in several triangles...

• This probability is structure-dependent, since how the $j$ interesect will affect the probability. – André Nicolas Jun 29 '13 at 20:08

If I understood correctly, you are given a vertex set, e.g. $V = \{1,2,3,4,5,6,7\}$. You pick $j_1 = \{1,2,4\}$ (for example), and $j_2 = \{2,1,3\}$. The edge set $\{12,14,24\}$ forms the first triangle, and the edge set $\{12,23,13\}$ forms the second triangle. The cardinality of the union of the two edge sets is $5$, and hence $P(\mathcal{E}_{j_1}\cap\mathcal{E}_{j_2}) = p^5$. Since you allow to pick $\mathcal{E}_j$s arbitrarily, I see no way but to calculate the edge sets, take their unions and then calculate the cardinality, raise $p$ to that cardinality.

• Would you agree that if I have $k$ such sets of three vertices I would have to consider all cases from all of those sets being disjoint to all being the same, which would lead to $\mathbb{P}(\cap_{j=1}^k \mathcal{E}_j)=\sum_{i=3}^k c_i p^i$ (where I am not sure about a combinatorial factor $c_i$)? – madison54 Jun 29 '13 at 21:37
• Yes, but then again, your factors $c_i$ may again depend on the specific nature of your $\mathcal{E}_i$s. I do not think you can find a "simple universal formula" that covers all the cases. – Lord Soth Jun 29 '13 at 21:40
• In fact, necessarily, $P(\cap_{j=1}^k \mathcal{E}_j) = p^l$ for some $l \leq 3k$ that depends on $\mathcal{E}_j$. If you care about asymptotic behavior of the probability that there is $k$ triangles ($\cup_{\mathcal{E}_1, \ldots, \mathcal{E}_{k}} \cap_{j=1}^k \mathcal{E}_j$), as long as $p$ is not "too large" the dominant term in the probability comes from edge-disjoint triangles. – D Poole Jul 1 '13 at 14:28