Consider a sequence of nonnegative weights \( (w_k)_{k\geq 1} \).
We build a sequence of trees \( (\mathcal{T}_n)_{n\geq 1} \) recursively as follows:
The tree \( \mathcal{T}_1 \) consists of a single vertex \( u_1 \) with weight \( w_1 \).
Assume the tree \( \mathcal{T}_{n-1} \) is constructed.
We choose a vertex of \( \mathcal{T}_{n-1} \) at random proportionally to its weight
and we add the vertex \( u_n \) with weight \( w_n \) as a child of this vertex.
The tree obtained this way is \( \mathcal{T}_{n} \).
In a joint work with
Delphin Sénizergues, we work under the assumption that
\( \sum_{i=1}^n w_i = \text{cst} \cdot n^{\gamma} + O(n^{\gamma-\varepsilon}) \),
for some \( \gamma,\varepsilon > 0 \).
We prove the following asymptotic development for the height of weighted recursive trees:
\[ \text{height}(\mathcal{T}_{n}) = \gamma e^\theta \log n - \frac{3}{2\theta} \log \log n + O(1), \]
where \(\theta\) is the single positive solution to \( \gamma (\theta e^\theta + 1 - e^\theta) = 1 \).
This is a behavior similar to the one appearing for the maximum of branching Brownian motion,
see here.
Pictures and movies
Below are pictures of weighted recursive trees with \( n=10000 \) vertices and different values of the parameter \(\gamma\).
The root is represented at the bottom.
The spacing between vertices at a given height is the same for the whole figure, so the width of a generation on the picture is proportional to its size.
The color of an edge represents the time where it has been added, using the viridis colormap,
from dark blue (first edges) to light green (last edges).
The pictures are followed by a video showing the construction of the tree.
These pictures illustrate in particular a result by Delphin Sénizergues concerning the profile of weighted recursive trees
(see here).
He proved that the profile converges to a Gaussian shape centered at height \(\gamma \log n\).
