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...

  • $\begingroup$ This probability is structure-dependent, since how the $j$ interesect will affect the probability. $\endgroup$ – 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.

  • $\begingroup$ 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$)? $\endgroup$ – madison54 Jun 29 '13 at 21:37
  • $\begingroup$ 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. $\endgroup$ – Lord Soth Jun 29 '13 at 21:40
  • $\begingroup$ 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. $\endgroup$ – D Poole Jul 1 '13 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.