13
$\begingroup$

Given a rooted tree $T$ and an integer $k \geq 1$, let $N_k(T)$ be the number of subtrees of $T$ containing the root and having exactly $k$ nodes (take $N_k(T)=0$ if $T$ has less than $k$ nodes).

Next, fix an integer $d \geq 2$, and let $T_d$ be the infinite $d$-ary rooted tree (every node has $d$ children). It is well-known (see, e.g. Stanley's "Enumerative combinatorics", theorem 5.3.10) that $$ N_k(T_d) = \frac{1}{k}{dk \choose k-1} < (ed)^{k-1} ~. $$ When $d=2$, these are simply the Catalan numbers.

Now suppose that $\mathcal{T}$ is a Galton–Watson tree with offspring distribution $B$ and $\mathbb{E}(B)=\mu \in (1,\infty)$.

What can be said about the behavior of $N_k(\mathcal{T})$, either in probability or in expectation, when the branching distribution $B$ may be unbounded?

In particular, it seems likely that under suitable assumptions on $B$, $N_k$ again grows exponentially in $k$. Is it the case, for example, that $N_k/(2e\mu)^{k-1} \to 0$ in expectation (or in probability), perhaps assuming that $B$ has sufficiently large exponential moments?

Perhaps the problem is more combinatorially tractable if one assumes that $B$ has a Poisson distribution? This special case is interesting to me.

$\endgroup$
1
  • 2
    $\begingroup$ For the case where $B$ has Poisson distribution with mean $d$, maybe it's possible to do something by comparing to the random graph $G(n,d/n)$? The expectation seems easier to compute in the graph case than the tree (roughly $n^{k−1}/(k-1)!$ choices for the vertices including your root, $k^{k-2}$ choices for the trees on those vertices, each occurring with probability $(d/n)^{k−1}$, giving a product which grows exponentially in $k$ for fixed $d$), and it feels like their behaviors should be similar if we let n be much larger than k. $\endgroup$ Jun 1, 2011 at 14:45

1 Answer 1

8
$\begingroup$

Let $p_n$ be the offspring distribution for $B$ and define $q_n = \sum_{m\ge n} p_m (m)_n$, where $(m)_n = m!/(m-n)!$ is the descending factorial.

(new paragraph to appease MO latex scripts). Then the expected number of copies of a rooted tree $\theta$ inside the Galton Watson tree $\mathcal{T}$ is given by $\prod_{v\in\theta} q_{d_v}$ (where $d_v$ does not count the parent of $v$.

This is seen by induction on $\theta$. Given the root degree in $\mathcal{T}$ is $m$, the number of ways to select $d$ children of the root is $(m)_d$. For each of these, the expected number of ways to embed the sub-trees of $\theta$ is given by the formula (induction hypothesis). Since $\mathcal{T}$ is Galton-Watson, these are independent, and the expectation is the product of expectations.

This gives an identity $F(z) = Q(zF(z)$ for the generating function of the expected number of trees with weight $z$ for each edge. It seems that for nice $p$'s the singularity should have the same algebraic type, and so the expected number of trees in $\mathcal{T}$ grows as $C n^{-3/2} z_c^{-n}$.

In the case of the Poisson-Galton-Watson tree, it is easy to see either from the above or by staring into (probability) space that the expected number of copies of any tree $\theta$ is just $\lambda^{|\theta|}$ (still counting edges), so the expectation is just $\lambda^n C_n\sim Cn^{-3/2}(4\lambda)^n$.

Computing higher moments is probably doable in the Poisson case, but seems less fun. I will wait for additional motivation before delving into computations, but if staringinto space yields anything I'll report here.

$\endgroup$
2
  • $\begingroup$ Can you say a few words about how you obtained the formula $\prod_{v\in\theta} q_{d_v}$? Thanks! $\endgroup$ Jun 6, 2011 at 9:31
  • $\begingroup$ This looks like it should work in fair generality, whenever $Q(z)$ behaves reasonably. Vertex weights might make the computations a little simpler than edge weights, I'll see. Thanks for the suggestion, Omer -- when I get around to working out some details I'll post an update. $\endgroup$ Jun 7, 2011 at 17:56

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.