2
$\begingroup$

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!

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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