expected number of cycles in a "random" bipartite directed graph

Question

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!

Answer 1

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.

Answer 2

You should try

Flajolet, P.; Odlyzko, A. (1990), "Random mapping statistics", Advances in Cryptology – EUROCRYPT '89: Workshop on the Theory and Application of Cryptographic Techniques, Lecture Notes in Computer Science, 434, Springer-Verlag, pp. 329–354.

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$.