# Distribution of cycles length in a graph

Given a random directed Graph G:

$$G=(V,E) \\ \lvert V \rvert = n , \lvert E \rvert = k$$

where for each vertex, either: $$d_{incoming}(v) = 1 , d_{outgoing}(v) = 1$$ meaning - for each incoming (outgoing) edge to vertex v, there is also an outgoing (incoming) edge from vertex v.

Or: $$d(v) = 0$$

What is the distribution of lengths of the longest cycles for this set of random graphs?

This question relates to the riddle presented in the last minute-physics video. (for the general case)

• Nice question. If it doesn't get an answer here after a few days, you should maybe flag it for migration to Mathematics. But please don't just repost it there as doing so will fragment answers and confuse people. – David Richerby Dec 9 '14 at 11:15
• What have you tried and where did you get stuck? What are your thoughts and motivations for this question? – Raphael Dec 9 '14 at 13:22
• @DavidRicherby "Nice" as in interesting, but certainly not SE-nice, isn't it? Do you see how to flesh it out? – Raphael Dec 9 '14 at 13:23
• @Raphael Does it need fleshing out? A brief survey of existing results in the field would be a reasonable answer. For example, Pósa has shown that, for a large enough constant $c$, a random graph with $n$ vertices and $cn\log n$ edges is asymptotically almost surely Hamiltonian ("Hamilton circuits in random graphs", Discrete Mathematics, 14:359-364, 1976). – David Richerby Dec 9 '14 at 14:38
• @DavidRicherby Can you provide an answer then? I'm not sure whether the question asks for an algorithm (text) or a "static" result (tags). – Raphael Dec 9 '14 at 15:03

## 1 Answer

When $k = n$ and self-loops are allowed, what you have is a random permutation. The expected length of the longest cycle in a permutation is known to be $\alpha n$ for $\alpha \approx 0.624$, see Shepp and Lloyd. If self-loops are not allowed then you will get a different constant $\beta$ that can probably be computed using the methods of Shepp and Lloyd.

When $k < n$, you just get a permutation on $k$ vertices, so instead of $\alpha n$ or $\beta n$ you would get $\alpha k$ or $\beta k$.