probability of embeddings in graph

Question

Setup: Let G be a graph on n vertices. Between each pair of vertices, with probability p there is a blue edge, and with probability 1 − p a red edge.

Question: Triangle distributions Let T be a triangle with three blue edges. For n = 2, 3, 4, 5, 6, 12, 24 and for n very large what is the probability P (|Emb(T , G)| = f) that the number of embeddings of T in G equals exactly f (for all f with 0 ≤ f ≤ n) ? If your answer would not be exact, can you say how good is your approximation?

Any ideas anyone?

Answer 1

This question could be rephrased as follows: If $G(n,p)$ is a random graph on $n$ vertices where each potential edge is present with probability $p,$ independent of other edges, then how many cycles of length 3 are present in $G(n,p)$?

The distribution of the number of cycles clearly should depend on the parameters $n$ and $p$. Exact formulas are hard to come by, but the following gives asymptotics for $n$ tending to $\infty,$ in the case that $p$ depends on $n$.

If $n p_n \to 0$ as $n \to \infty$, then $$Prob(\# \text{ of triangles in }G(n,p_n)=0) \to 1.$$ Furthermore, if $n p_n \to c$, where $c$ is a positive constant, then for each $k \in \{0, 1, 2, \ldots\}$, $$ P(\# \text{ of triangles in }G(n,p_n)=k) \to e^{-c^3/6} \frac{(c^3/6)^k}{k!}. $$

(This information can be found in the standard textbooks "Random Graphs" by Bollobas and "Random Graphs" by Janson, Luczak and Rucinski)