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)

Improve this question
$\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
    Commented Dec 9, 2014 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
    Commented Dec 9, 2014 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
    Commented Dec 9, 2014 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
    Commented Dec 9, 2014 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
    Commented Dec 9, 2014 at 15:03

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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