Limits of biconditioned Bienaymé–Galton–Watson trees
Vanessa Dan · 2025
Read Limits of biconditioned Bienaymé–Galton–Watson trees by Vanessa Dan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22135.txt.
Introduction
Vanessa Dan studies random family trees in a 2025 math paper. The trees follow the classic Bienaymé–Galton–Watson model, where each person has a random number of children. Dan pins down two totals at once: the whole tree size plus either its leaves or its inner nodes. She asks what shape a huge tree takes under each double condition.
The leaf condition gives one universal limit, the same for every offspring rule. The inner-node condition splits into many outcomes, from one giant hub with most children on it to long stretched trees. Which outcome appears depends on the offspring rule's tail. Random walk tools and counting methods from combinatorics carry the proofs.
Catalog record
| CREATOR | Vanessa Dan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-22135
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Limits of biconditioned Bienaymé–Galton–Watson trees Vanessa Dan Abstract We study the limiting behavior of a Bienaymé–Galton–Watson tree conditioned to have a large number of vertices and either a fixed number of leaves or a fixed number of internal nodes. The first biconditioning gives a universal result with respect to the offspring distribution. In contrast, the second case leads to a variety of limiting behaviors, ranging from condensation phenomena to more elongated tree structures, depending on the properties of the offspring distribution. To prove these results, we use tools from conditioned random walk theory and from analytic combinatorics. 1 Introduction In this article, we are interested in the asymptotic behavior of Bienaymé–Galton–Watson trees (BGW trees) conditioned on having a large number of vertices with a fixed number of leaves or internal nodes. Scaling limits of BGW trees were initiated by Aldous [ Ald91a , Ald91b , Ald93 ] who proved that the rescaled critical BGW tree with finite-variance offspring distribution, conditioned on having a large total number of vertices, converges to a continuous random tree known as the Brownian Continuum Random Tree (CRT). The theoretical framework around this notion of convergence has since been well established (see the survey article [ LG05 ] ). This convergence result has been extended to more general settings. In particular, Duquesne [ Duq03 ] (see also [ Kor13 ] ) studied the case where the offspring distribution has infinite variance, and showed that the scaling limit of a critical Bienaymé–Galton–Watson tree whose offspring distribution lies in the domain of attraction of a stable law is a continuous random tree, known as the stable tree. It is worth noting that the case where the mean number of children is strictly greater than 1 is similar and leads to the same results. However, if the mean is strictly less than 1, the geometry of a tree conditioned to be large can be very different and can lead to a condensation phenomenon [ Kor15 ] . Often motivated by applications to other random combinatorial structures, many other types of conditioning have also been considered, such as maximum height [ LG10 ] , maximum degree [ He17 ] , generation sizes [ ABD20 ] , or the total number of vertices with fixed degrees [ Kor12 , Riz15 , Thé20 ] . While the asymptotic behavior of conditioned BGW trees is now well understood, many biconditioned cases (i.e. conditioning on both the total number of vertices and the number of leaves), remain largely unexplored. Nonetheless, several works have addressed specific biconditioned models, beginning with Labarbe and Marckert who studied the case of the uniform distribution, in which both the number of leaves k_{n} and the number of internal nodes n-k_{n} tend to infinity [ LM07 ] . They showed that, although the normalization factor must be adjusted depending on the number of imposed leaves, the scaling limit remains the same as in the single-conditioning case: the Brownian CRT. Then, Kargin considered BGW trees conditioned on both the total number of vertices n and the number of leaves k_{n} , focusing on the regime where both k_{n} and n grow to infinity and k_{n}=\alpha n+O(1) , with \alpha\in(0,1) [ Kar23 ] . Under the assumption of exponential decay of the offspring distribution, he proved that the rescaled tree once again converges in distribution to the Brownian CRT. Finally, motivated by questions related to random maps, Kortchemski and Marzouk have recently obtained results [ KM23 ] on the scaling limits of the Łukasiewicz walk of such trees. The results in [ KM23 ] suggest that new scaling limits should emerge. In this article, we contribute to this line of research by studying the scaling limits of BGW trees under several new biconditioning regimes. We specifically focus on the case of biconditioning on the total number of vertices and either the number of leaves (Section 3 ) or the number of internal nodes (Sections 5 - 8 ) is a fixed integer k while the total number n of vertices tends to infinity. Fixed number of leaves. First, to ensure that the trees we consider are well-defined, we assume that the offspring distribution \mu satisfies \mu(1)>0 . To study the biconditioned \mu -BGW tree, we decompose the structure of a tree with n vertices and k leaves into two components: a reduced tree and a sequence of single-child ancestors. The reduced tree of a , denoted by R(a) , is obtained by removing all vertices in a that have exactly one child. For each vertex u in R(a) , we count the number of consecutive single-child vertices in a that lie between u and its parent in R(a) , or between u and the root of a if u is the root of R(a) . We define the sequence of single-child ancestors of a , denoted by L(a) , the sequence of these numbers when R(a) is visited in lexicographic order. These two definitions are illustrated in Figure 1 below. Figure 1: An example of a tree a with its reduced tree R(a) and its sequence of single-child ancestors L(a) . We will see in Section 3 that R(a) and L(a) completely characterize a tree a with n vertices and k leaves. Thus, studying the limit behavior of a biconditioned \mu -BGW tree is equivalent to studying the joint limit behavior of its reduced tree and its sequence of single-child ancestors. Theorem 1.1 . Let \mu be an offspring distribution with \mu(1)>0 and \mu(2)>0 . Let k\geq 1 and T_{n}^{k} a \mu -BGW tree conditioned to have n vertices and k leaves. Then, we have the following convergence in distribution: \Bigl(R(T_{n}^{k}),\frac{L(T_{n}^{k})}{n}\Bigl)\xrightarrow[n\rightarrow+\infty]{(d)}\bigl(R^{k},\Delta\bigr) where R^{k} is a uniform random binary tree with k leaves and \Delta is a Dirichlet random variable with parameter (1,\ldots,1) independent of R^{k} . See Figure 2 for an illustration. Note that if \mu(2)=0 , Theorem 1.1 cannot hold as this would imply that \mathbb{P}(R^{k}_{n}=b)=0 for all binary trees b with k leaves . In that case, let i_{0}\geq 3 be the smallest integer such that \mu(i_{0})>0 . It is worth noting that if k-1 is a multiple of i_{0}-1 , we get that R_{n}^{k} converges in distribution as n tends to infinity to a uniform random i_{0} -ary tree with k leaves. The main result of Section 3 , Theorem 3.4 , extends Theorem 1.1 to any integer k . Figure 2: Illustration of the limit behavior of a \mu -BGW with n nodes and k leaves. Fixed number of internal nodes. Unlike the first biconditioning, the limit here is not universal and depends sensibly on the properties of the offspring distribution \mu . As in the previous biconditioning, we begin by decomposing trees with n vertices and k internal nodes into two components: a reduced tree and a list of leaves. The reduced tree R(a) of a is the tree obtained by removing all leaves from a and its sequence of leaves L(a)\coloneqq(L_{1}(a),\ldots,L_{2k-1}(a)) is the sequence of length 2k-1 such that for every i in [\![1,2k-1]\!] , the i -th element of the sequence equals the number of leaves of a grafted in the i -th corner of R(a) if the corner surrounds an internal node of R(a)