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…
Best Answer
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.