# expected number of cycles in a “random” bipartite directed graph

Consider a "random" bipartite directed graph where (1) on each side, the set of vertices has cardinality n and (2) for each vertex i, we add one (and only one) directed edge i->j at random (drawn uniformly over the n possible directed edges).

Clearly, for all n, and any possible realization of the random graph, there is at least one cycle.

But what's the expected number of cycles when n tends to infinity? Given k (even), what's the expected number of cycles of size k when n tends to infinity?

I suppose this problem is standard... I would be greatful if one could give me references on this.

Thanks!

-

There are $$\frac{\prod_{i=0}^{k-1}(n-i)^2}{k}$$ possible directed cycles with $2k$ vertices. Each such cycle occurs with probability $n^{-2k}$, so the exact expectation of the number of cycles is $$\sum_{k=1}^n \frac{\prod_{i=0}^{k-1}(n-i)^2}{kn^{2k}} = \sum_{k=1}^n \frac{\prod_{i=0}^{k-1}(1-i/n)^2}{k}.$$ As $n\to\infty$, that sum is asymptotic to the integral $$\int_1^\infty \exp(-x^2/n)/x~dx = \left[ -\frac12 Ei(1,x^2/n) \right]_1^\infty = \frac12\log n + O(1),$$ where $Ei$ is the exponential integral function and I'm relying on Maple a bit.
They don't solve the same problem, exactly — they look at a non-bipartite random graph where each vertex has a single uniformly random outgoing edge, rather than bipartite graph — but it's similar enough that it might be helpful to you. They show that the expected number of cycles (or equivalently components) is $\tfrac{1}{2}\log n$.