MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let G be a directed graph on N vertices chosen at random, conditional on the requirement that the out-degree of each vertex is 1 and the in-degree of each vertex is either 0 or 2. The "periodic" points of G are those contained in a cycle. What do we know about the statistics of G? For instance, what is the mean number of periodic points, and how do the cycle lengths look?

By comparison, a random directed graph with all out-degrees 1 (which is to say, the graph of a random function from vertices to vertices) has on order of sqrt(N) periodic points on average.

(Motivation: the graph of a quadratic rational function f acting on P^1(F_q) looks like this, and I'm wondering what the "expected" dynamics are.)

share|cite|improve this question
up vote 3 down vote accepted

Let $G$ be a directed graph on $N$ vertices such that the out-degree of each vertex is 1 and the in-degree is either 0 or $n$. Letting $N=nt$, there are $t$ vertices with in-degree $n$ and $(n-1)t$ vertices with in-degree 0. Assuming the vertices are labeled, the number of such graphs is $$ \binom{nt}{t}\frac{(nt)!}{(n!)^t}. $$ For $1\leq m\leq t$, the number of such graphs with a fixed $m$-cycle is $$ \binom{nt-m}{t-m}\frac{(nt-m)!}{((n-1)!)^m(n!)^{t-m}}, $$ so the number of $m$-periodic points amongst all such graphs is $$ m\cdot\binom{nt-m}{t-m}\frac{(nt-m)!}{((n-1)!)^m(n!)^{t-m}}\cdot\frac{(nt)!}{m(nt-m)!}=\binom{nt-m}{t-m}\frac{(nt)!}{((n-1)!)^m(n!)^{t-m}}. $$ Summing over $1\leq m\leq t$, the average we want is $$ \binom{nt}{t}^{-1}\sum_{m=1}^{t}{n^m\binom{nt-m}{t-m}}=-1+\binom{nt}{t}^{-1}\sum_{m=0}^{t}{n^m\binom{nt-m}{t-m}}. $$ When $n=1$, the average is $t$ (since all points would be periodic). When $n=2$, as in the question, the sum is $$ -1+\frac{4^t}{\binom{nt}{t}}\sim-1+\sqrt{\frac{\pi}{2}}\sqrt{N}, $$ so the number of periodic points does indeed look random. When $n>2$, I haven't found the identity I need yet.

share|cite|improve this answer

To calculate expected numbers of cycle of each length, you should be able to just wade in and use Stirling's approximation to deal with the results.

Let's write $N=2t$. Then there are $t$ vertices with indegree 0 and $t$ with indegree 2. The number of such graphs is $(2t)!/2^t$.

If $a_1,\ldots,a_m$ are vertices with indegree 2, then the number of ways that they can be a cycle (in that order) is $$\binom{2t-m}{m}\frac{(2t-2m)!}{2^{t-m}},$$ since we first choose other inputs for these vertices, and then deal with what's left.

Then the expected number of $m$-cycles is obtained by multiplying that by $t!/(t-m)!$ and dividing by the number of such graphs. So you can get an exact formula, and then deploy Stirling on it.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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