Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.