patternMinor
Distribution of cycles length in a graph
Viewed 0 times
distributiongraphcycleslength
Problem
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)
$$
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)
Solution
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$.
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$.
Context
StackExchange Computer Science Q#34054, answer score: 4
Revisions (0)
No revisions yet.