Dynamics of a random "quadratic" directed graph

Question

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

Answer 1

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.

Answer 2

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.