Scaling limit of trees with vertices of fixed degrees and heights

Imagine you are looking at a massive, sprawling family tree. In this tree, every person (vertex) has two specific traits:

How many children they have (their degree).
How many generations down they are (their height).

Usually, when mathematicians study random trees, they might fix the total number of children in the whole family but let the specific heights be random. Or they might fix the heights but let the children count vary.

This paper asks a very specific question: What happens if we fix both the number of children and the exact generation for every single person in a giant, random family tree?

The authors, Arthur Blanc-Renaudie and Emmanuel Kammerer, discovered that if you zoom out far enough (scaling up), these rigid, complicated trees don't just look like messy scribbles. Instead, they smooth out into a beautiful, predictable, continuous shape. They call this shape a Limit Tree.

Here is the breakdown of their discovery using simple analogies:

1. The "Zoom Out" Effect

Imagine taking a photo of a forest. From up close, you see individual leaves, twigs, and bark. It looks chaotic. But if you fly up in a helicopter and zoom out, the forest looks like a smooth green carpet with a specific texture.

In this paper, the "forest" is a random tree with fixed rules. The "helicopter view" is the scaling limit. The authors proved that no matter how you arrange the specific rules for the children and generations (as long as they follow certain natural patterns), the tree will always settle into a specific, smooth mathematical shape.

2. The Two Ways Families Merge

To understand the shape of this limit tree, the authors looked at how random people in the tree find their way back to the root (the ancestor). They realized there are two ways these paths "merge" (coalesce):

The "Small Town" Merge (Small Degrees): Imagine a small village where everyone has 2 or 3 children. If you pick two random people, their paths to the root might merge because they happened to share a common grandparent. This happens frequently but slowly, like a gentle drizzle. The authors call this the $\rho$ (rho) factor. It's a steady, continuous flow of connections.
The "Big Boss" Merge (Large Degrees): Now imagine a massive corporation where one CEO has 1,000 direct reports. If you pick two random people, there's a high chance they both report to that one CEO. Their paths merge instantly at that one huge node. This is like a sudden, heavy rainstorm. The authors call this the $\Theta$ (theta) factor. It represents "jumps" or sudden connections caused by very popular ancestors.

The limit tree is a mix of these two: a smooth background of small connections punctuated by sudden, massive jumps where huge families connect.

3. The "Trail" Analogy

To prove the tree looks like this, the authors used a clever trick. Instead of tracking one random person, they imagined sending out a group of $k$ explorers (a "trail") from the top of the tree down to the root.

They watched how these explorers' paths merged.
They proved that if you have enough explorers, the "empty space" between them gets filled in.
By showing that these trails stay close together and cover the whole tree, they proved the entire tree has a well-defined shape, not just a few random points.

4. The Real-World Application: The "Changing Environment"

The paper isn't just about abstract math; it applies to Bienaymé–Galton–Watson trees in varying environments.

Think of a species of bacteria evolving.

In a "good" environment (summer), they might reproduce rapidly (high degree).
In a "bad" environment (winter), they might barely reproduce (low degree).
The environment changes every generation.

If you look at the family tree of this bacteria over a long time, the rules for reproduction change constantly. The authors' work shows that even with these changing rules, if you look at the "profile" (how many people are in each generation), you can predict the overall shape of the entire evolutionary tree.

Summary

The Problem: What does a giant random tree look like if we force every person to have a specific number of kids at a specific generation?
The Solution: It converges to a smooth, continuous shape (a "Limit Tree").
The Mechanism: The shape is determined by how paths merge: either slowly through many small families or instantly through a few giant families.
The Metaphor: It's like taking a chaotic, pixelated image of a forest and realizing that, from a distance, it forms a perfect, smooth landscape defined by the "drizzle" of small families and the "storms" of large ones.

This work is a bridge between rigid, discrete rules (fixed degrees) and fluid, continuous mathematics (scaling limits), helping us understand the geometry of complex, evolving systems.

Here is a detailed technical summary of the paper "Scaling limit of trees with vertices of fixed degrees and heights" by Arthur Blanc-Renaudie and Emmanuel Kammerer.

1. Problem Statement

The paper investigates the scaling limits of large uniform random trees where the degree (number of children) and the height (distance from the root) of every vertex are fixed in advance.

Model: Consider a sequence of trees $T_n$ constructed layer by layer. For each height $i$ , there is a prescribed sequence of degrees $(d^n_{i,j})_{j \ge 1}$ . The total number of vertices at height $i$ is $D^n_i = \sum_j d^n_{i,j}$ . The tree is formed by uniformly and independently attaching the $D^n_i$ vertices at height $i+1$ to the vertices at height $i$ such that vertex $(i,j)$ receives exactly $d^n_{i,j}$ children.
Goal: Determine the weak convergence of the rescaled metric space $T_n/n$ (where edge lengths are scaled by $1/n$) equipped with the uniform probability measure on its vertices.
Context: This model generalizes uniform trees with fixed degree sequences (where heights are random) and conditioned Bienaymé–Galton–Watson (BGW) trees in varying environments. The specific constraint of fixing heights introduces significant complexity compared to standard models, as the genealogy structure is rigidly determined by the profile of degrees across heights.

2. Methodology

The authors employ a coalescent process approach to analyze the genealogies of random vertices. The core idea is to study the paths from random leaves to the root and characterize how these paths merge (coalesce) as one moves down the tree.

A. The Limiting Coalescent Process

The authors define a continuous-time growth-coalescent process that describes the merging of $k$ particles (representing random vertices) as time $t$ (representing normalized height) goes from 1 (leaves) to 0 (root). The merging occurs via two distinct mechanisms:

Small Merges (Small Degrees): Pairs of lineages merge at a rate determined by a locally finite measure $\rho$ on $(0,1)$ . This corresponds to coalescence at vertices with small degrees relative to the total population at that height.
Large Merges (Large Degrees): At specific heights $t$ , if there are vertices with "macroscopic" degrees (proportional to the total population), multiple lineages can merge simultaneously. This is governed by a sequence of parameters $\Theta = (\theta_j(t))_{j \ge 1}$ , where $\theta_j(t)$ represents the relative size of the $j$ -th large degree at height $t$ .

B. Convergence Framework

To prove convergence, the authors establish two types of convergence:

Gromov–Prokhorov (GP) Convergence: Focuses on the convergence of distance matrices between a finite number of random vertices. This is achieved by proving the convergence of the discrete growth-coalescent process associated with $T_n$ to the continuous limit process defined above.
Gromov–Hausdorff–Prokhorov (GHP) Convergence: A stronger topology requiring the entire metric space to converge. This necessitates proving tightness (specifically, "leaf-tightness"), ensuring that the random vertices densely cover the tree.

C. Key Technical Tools

Profile Convergence: Assumption $(Lim_\nu)$ ensures the empirical distribution of heights converges to a measure $\nu$ .
Degree Scaling: Assumptions $(Lim_\rho)$ and $(Lim_\Theta)$ describe the convergence of the "merging rates" derived from small and large degrees, respectively.
Separation of Large Degrees: Assumption $(Lim_\neq)$ ensures that large-degree vertices at the same height in the limit correspond to distinct heights in the finite tree, preventing pathological overlaps.
Tightness Condition (TightGHP): A technical integrability condition involving the function $\tau^n_i(k)$ , which acts as a discrete analog to the Laplace exponent of Lévy trees. It ensures that the tree does not have "gaps" that would prevent GHP convergence.

3. Key Contributions

1. General Scaling Limit Theorem (Theorem 1.2 & 1.3)

The paper provides a comprehensive set of conditions under which the rescaled tree $T_n/n$ converges to a random measured metric space $\mathcal{T}(\nu, \rho, \Theta)$ .

GP Convergence: Holds under conditions $(Lim_\nu), (Lim_\rho), (Lim_\Theta), (Lim_\neq)$ , and $(TightGP)$ .
GHP Convergence: Holds if, in addition, the height $h_n \sim n$ and the tightness condition $(TightGHP)$ is satisfied.

2. Construction of the Limit Space

The limit space is constructed implicitly via the coalescent process. The distance between two random vertices is determined by the time of their most recent common ancestor (MRCA) in the coalescent. The paper rigorously proves the existence of this limit space by establishing leaf-tightness (Proposition B.1), ensuring the limit is a well-defined real tree.

3. Application to BGW Trees in Varying Environments

A major application is the derivation of scaling limits for Bienaymé–Galton–Watson trees in varying environments (GWVE) conditioned on their total population profile and offspring degrees.

The authors link the parameters of the GWVE (drift $\alpha$ , variance $\beta$ , and jump measure $\mu$ ) to the coalescent parameters $(\nu, \rho, \Theta)$ .
Specifically, the profile of the tree converges to a process $X(t)$ , and the large degrees in the tree correspond to the positive jumps of $X(t)$ .
This generalizes previous results (e.g., by Kurtz, Bansaye-Simatos) by providing the full metric scaling limit (GHP) rather than just the profile or genealogy of a single generation.

4. Main Results

Theorem 1.2: Under the convergence of the profile ( $\nu$ ), the merging rates of small degrees ( $\rho$ ), and the structure of large degrees ( $\Theta$ ), the sequence of trees converges in distribution in the Gromov–Prokhorov topology to a random measured metric space.
Theorem 1.3: Under the additional tightness condition $(TightGHP)$ (which controls the local density of vertices), the convergence strengthens to the Gromov–Hausdorff–Prokhorov topology.
Corollary 5.1: For GWVE trees, if the rescaled profile converges to a process $X(t)$ with specific properties (continuous drift/variance, specific jump structure), the tree converges to the limit space defined by the jumps of $X$ and its continuous components.

5. Significance and Impact

Unification of Models: The paper unifies the study of trees with fixed degrees, fixed heights, and varying environments. It shows that the scaling limit is determined by the interplay between the "bulk" of small degrees (diffusive behavior) and the "spikes" of large degrees (jump behavior).
Beyond Brownian Limits: Unlike many previous works that focus on Brownian Continuum Random Trees (CRT), this framework handles non-Brownian limits, including stable trees and trees with heavy-tailed degree distributions, by incorporating the measure $\rho$ and the sequence $\Theta$ .
Rigorous Treatment of Heights: By fixing heights, the authors address a more constrained model than standard configuration models. The techniques developed (specifically the $k$ -trail approximation and the analysis of coalescence rates at specific heights) provide new tools for analyzing random structures with rigid geometric constraints.
GWVE Applications: The results offer a powerful tool for analyzing the geometry of branching processes in varying environments, a topic of high relevance in population genetics and statistical physics, by linking the macroscopic tree geometry directly to the microscopic offspring distribution parameters.

In summary, this paper establishes a robust theoretical framework for the scaling limits of highly structured random trees, bridging the gap between discrete combinatorial models and continuous random metric spaces, with direct applications to complex branching processes.