4
$\begingroup$

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)

$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Dec 9 '14 at 11:15
  • $\begingroup$ What have you tried and where did you get stuck? What are your thoughts and motivations for this question? $\endgroup$ – Raphael Dec 9 '14 at 13:22
  • $\begingroup$ @DavidRicherby "Nice" as in interesting, but certainly not SE-nice, isn't it? Do you see how to flesh it out? $\endgroup$ – Raphael Dec 9 '14 at 13:23
  • 1
    $\begingroup$ @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). $\endgroup$ – David Richerby Dec 9 '14 at 14:38
  • $\begingroup$ @DavidRicherby Can you provide an answer then? I'm not sure whether the question asks for an algorithm (text) or a "static" result (tags). $\endgroup$ – Raphael Dec 9 '14 at 15:03
4
$\begingroup$

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

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