I asked this question on MSE a few weeks ago but got no response.


The question arose out of some research in group theory on random group presentations. The actual question is more complicated, but the following captures the essence of it. It is similar to the birthday coincidence problem, but involves a condition on triples rather than pairs.


We have a set $A$
of size $n$ and we choose a set $P$ of $r$ random ordered pairs of distinct elements of $A$. I would like to estimate the probability, as a function of $n$ and $r$, that there exist three elements of $P$ of the form $(a,b),(b,c),(c,a)$ for some $a,b,c \in A$.



A condition on triples of elements in a random collection of ordered pairs
In the comments to your question, @MattF. is correct, and @IlyaBogdanov is also spot on (in probabilistic combinatorics, this approximation comes as a routine knee-jerk reaction). This problem is extremely well-known. I'll summarize very quickly, but you can find more online by searching "probability random graph has a triangle." Strictly speaking, you are actually considering this for directed graphs, but the idea is the exact same. Here's an outline.


Let $p= r/(n-1)n$. Then we'll approximate the answer (very well) by instead viewing it as independently selecting each ordered pair with probability $p$ [this approximation is extremely good unless say both of the parameters $r$ and $n$ are extremely small].


Let $X$ be the number of directed triangles that show up. Then by linearity of expectation
$$
\mathbb{E}[X] = 2 \frac{n(n-1)(n-2)}{6} p^3 \sim (np)^3 / 3,
$$
where that multiplication by $2$ is because we are considering *directed* triangles.


* If $np$ is very large (e.g., going to infinity), then it turns out that $X$ obeys a central limit law (and even a local limit law too). So if $np$ is very large, then you can mostly just pretend $X$ is just a binomial random variable with parameters of $n^3 /3$ trials and each is a success with probability $p^3$ [this works well for the meatiest parts of the distribution, but the tail probabilities will be off]. For you though, $P(X=0)$ will be exceedingly rare.
* If $np$ is roughly a constant, then $X$ is basically going to have a Poisson distribution with mean $\lambda = (np)^3 / 3$. So $P(X=0) \approx e^{-\lambda}$.
* If $np$ is very small (tending to 0) then it will be very likely that $X=0$.


