# Expected number of triangles in a random graph of size $n$

Consider the set $V = \{1,2,\ldots,n\}$ and let $p$ be a real number with $0<p<1$. We construct a graph $G=(V,E)$ with vertex set $V$, whose edge set $E$ is determined by the following random process: Each unordered pair $\{i,j\}$ of vertices, where $i \neq j$, occurs as an edge in $E$ with probability $p$, independently of the other unordered pairs.

A triangle in $G$ is an unordered triple $\{i,j,k\}$ of distinct vertices, such that $\{i,j\}$, $\{j,k\}$, and $\{k,i\}$ are edges in $G$.

Define the random variable $X$ to be the total number of triangles in the graph $G$. Determine the expected value $E(X)$.

• Next time please choose a more descriptive title for your question. – MJD Mar 28 '14 at 14:27

## 1 Answer

Set $t\stackrel{\rm def}{=}\binom{n}{3}$, fix any ordering of the $t$ possible sets of 3 nodes, and consider accordingly $X_1,\dots,X_t$ the indicator random variables where $X_j$ is equal to $1$ iff the $j$-th set defines a triangle. You are interested in $\mathbb{E}\sum_{j=1}^t X_j$, where the expectation is taken over the $\binom{n}{2}$ i.i.d. draws defining the edges.

By linearity of expectation, $$\mathbb{E}\sum_{j=1}^t X_j = \sum_{j=1}^t \mathbb{E} X_j = t \mathbb{E} X_1 = tp^3$$ as all $X_j$'s are identically distributed (for the second equality).

• this approach is nice, but I may have missed something. Are the $X_i$'s really independent? For instance, if I know that $\{1,2,3\}$ define a triangle, shouldn't that increase my estimate of the probability that $\{2,3,4\}$ defines a triangle because I know that at least one of the required edges is there? I'm sure the problem is just that I'm missing something though ... – Rookatu Mar 28 '14 at 18:39
• Sorry -- the $X_j$ are not independent, though they are identically distributed (which is what I needed for the second equality). Independence is not needed at all, the only real property used is the linearity of expectation. – Clement C. Mar 28 '14 at 18:44
• Okay, thanks. And again, nice solution :) – Rookatu Mar 28 '14 at 18:45
• This is really nice! I couldn't believe it could be so simple until I calculated it the long way for $n=4$ and got the same answer. – MJD Mar 28 '14 at 21:46