Limits of descent-biased trees

Source abstract

We investigate scaling and local limits of random trees biased according to their number of descents. A descent in a rooted labeled tree $t$ is a parent-child pair such that the label of the parent is greater than the label of the child, and the total number of descents is denoted by $\mathrm{des}(t)$. For $n \geq 1$ and $q_n \geq 0$, we consider the probability measure on trees of size $n$ where each tree $t$ is chosen with a probability proportional to $q_n^{\mathrm{des}(t)}$. We study the resulting random tree $\mathcal{T}_n^{(q_n)}$ properly rescaled as $n \to \infty$, and focus on two regimes for the bias parameter $q_n$. When $q_n = q \in (0,1]$ is fixed, we prove that $\mathcal{T}_n^{(q)}$ converges in distribution to the Brownian Continuum Random Tree. When $q_n = a/n$ for some fixed $a > 0$, we prove that $\mathcal{T}_n^{(q_n)}$ converges in distribution to a random non-trivial dendron constructed from a Poisson-Dirichlet sequence. We complement these results with a description of the Benjamini-Schramm local limit of $\mathcal{T}_n^{(q_n)}$ in all regimes of parameters. Our proofs rely on analytic combinatorics to find the asymptotics of certain statistics of the tree, and on a probabilistic analysis of the structure of descent-biased random trees.