Rotating random trees with Skorokhod's $M_1$ topology

Imagine you have a giant, tangled ball of yarn representing a family tree. In mathematics, we often study these trees to understand how they grow, how big they get, and what they look like when they become infinitely large.

This paper is about a specific trick mathematicians use to "rotate" these trees and see what happens. It turns out that how the tree looks after the rotation depends entirely on the "personality" of the tree's growth rules.

Here is the story of the paper, broken down into simple concepts.

1. The Problem: Broken Rulers and Jumpy Trees

Usually, when mathematicians study these random trees, they draw them using smooth, continuous lines (like a gentle hill). This works great for trees that grow in a "normal" way (like a Gaussian distribution, where most branches are average size).

However, some trees grow in a "wild" way. They have massive, sudden jumps in size—think of a tree where one branch suddenly sprouts a thousand leaves at once. In math, these are called càdlàg functions (a fancy word for "jumpy but predictable").

The problem is that the standard tools used to measure these trees (like a smooth ruler) break when the tree jumps. You can't measure a jump with a smooth ruler; you need a flexible, stretchy tape measure.

The Paper's Innovation:
The author introduces a new way to measure these "jumpy" trees using Skorokhod's M1 topology.

The Analogy: Imagine you are drawing a picture of a jagged mountain range.
- Old Method (J1 Topology): You try to draw the line exactly as it is. If there is a sudden cliff, your pen has to jump. If you try to compare two mountains with cliffs in slightly different spots, the lines look totally different, even if the mountains are similar.
- New Method (M1 Topology): Instead of drawing the line, you imagine a string that can slide up and down the cliff face. You stretch the string to fill in the gap. Now, even if the cliffs are in different spots, the "stretched string" looks very similar. This allows the author to compare wild, jumpy trees with smooth ones without the math breaking.

2. The Magic Trick: The Rotation

The paper focuses on a specific operation called Rotation.

The Analogy: Imagine a family tree where every person has a list of children.
- The Rotation: You take the first child and make them the new "head" of the family. Then, you take the second child and make them the "spouse" of the first. The third child becomes the "spouse" of the second, and so on. You are essentially turning a vertical family tree into a horizontal "spine" with branches sticking out the side.
The Question: If you take a huge, random tree and perform this rotation, what does the new tree look like? Does it look like the old one, just stretched? Or does it turn into something completely alien?

3. The Discovery: Two Different Worlds

The author discovers that the answer depends on the "genetics" of the tree (the offspring distribution).

Case A: The "Normal" Tree (Gaussian Case)

If the tree grows in a standard, predictable way (like a bell curve), the rotation is harmless.

The Result: The rotated tree looks exactly like the original tree, just stretched out.
The Metaphor: Imagine taking a rubber band and stretching it by a factor of 2. It's still a rubber band; it just looks longer. The rotation acts like a simple zoom lens.

Case B: The "Wild" Tree (Stable Case)

If the tree has "wild" growth rules (where huge jumps are possible), the rotation is transformative.

The Result: The rotated tree does not look like the original tree at all. It becomes a completely new, strange object.
The Metaphor: Imagine taking a ball of yarn and spinning it. In the "normal" case, it just gets longer. In the "wild" case, the spinning turns the yarn into a looptree—a structure made of loops and circles glued together. The original tree was a branching structure; the rotated tree is a web of loops.

4. Why This Matters

The author proves that these "rotated" trees are actually the same as Stable Looptrees, which are famous objects in probability theory.

The Connection: The paper shows that the "rotated" tree is a "spanning tree" of the looptree.
The Metaphor: Imagine a city with a complex network of circular roads (the looptree). The rotated tree is like a specific set of streets you can drive on that connects every neighborhood without ever going in a circle. It's a skeleton of the loop-city.

5. The "Mirror" Twist

The paper also looks at a "Co-rotation" (a mirror image of the rotation).

The Surprise: While the "Rotation" turns a wild tree into a looptree, the "Co-rotation" keeps the tree looking like the original, even though the math behind it is different. It's like looking in a mirror: the reflection looks the same, but the way the light bounces off it is totally different.

Summary

This paper is a bridge between two worlds:

Smooth, predictable trees (where rotation just stretches them).
Wild, jumpy trees (where rotation turns them into loop-based structures).

The author built a new mathematical "tape measure" (Skorokhod's M1 topology) that can handle the jumps, allowing them to prove that when you rotate a wild tree, it doesn't just get bigger—it fundamentally changes its shape into a new, beautiful, loop-filled object.

Here is a detailed technical summary of the paper "Rotating random trees with Skorokhod's M1 topology" by Antoine Aurillard.

1. Problem Statement and Motivation

The paper addresses the scaling limits of Bienaymé-Galton-Watson (BGW) trees conditioned to have a large number of vertices ( $n$ ), specifically focusing on the geometric effects of a combinatorial operation known as rotation (denoted as $\text{Rot}$ ).

The Rotation: $\text{Rot}$ is a bijection between plane trees with $n$ vertices and binary plane trees with $n$ leaves. It was previously studied by Marckert [Mar04] for uniform plane trees (where the offspring distribution is geometric). Marckert showed that for uniform trees, the rotation acts asymptotically as a dilation (scaling of distances) of the original tree.
The Gap: It was unknown whether this "dilation" property holds for general critical BGW trees where the offspring distribution $\mu$ $μ$ lies in the domain of attraction of a stable law with index $\alpha \in (1, 2]$ $α \in (1, 2]$ .
- If $\alpha = 2$ (finite variance), the limit is the Brownian Continuum Random Tree (CRT).
- If $\alpha \in (1, 2)$ (infinite variance), the limit is an $\alpha$ -stable tree.
The Challenge: The encoding processes (contour, height, Łukasiewicz walks) of rotated trees often exhibit discontinuities (jumps) in the limit when $\alpha < 2$ . Standard functional convergence tools (Skorokhod's $J_1$ topology) fail to handle these jumps when comparing processes with different jump structures. The paper seeks to establish the scaling limits of $\text{Rot}(T_n)$ and determine if the limit is a simple dilation of the original tree $T_n$ or a fundamentally different geometric object.

2. Methodology

The paper employs a two-pronged approach: extending the coding of random trees to discontinuous functions and using combinatorial relations to compare encoding processes.

A. Extension of R-tree Coding via Skorokhod's M1 Topology

The core technical innovation is the extension of the classical coding of measured $\mathbb{R}$ -trees by continuous excursion functions to càdlàg (right-continuous with left limits) excursion functions.

Parametric Representations: The author utilizes the concept of parametric representations underlying Skorokhod's $M_1$ topology. A parametric representation $(\chi, \tau)$ of a function $x$ fills the discontinuities of $x$ with vertical segments, creating a continuous path in the completed graph.
Continuity Results: The paper proves that the map from a càdlàg excursion $x$ $x$ to the associated measured $\mathbb{R}$ $R$ -tree $(T_x, \mu_x)$ $(T_{x}, μ_{x})$ is continuous with respect to the $M_1$ $M_{1}$ topology on the function space and the Gromov-Hausdorff-Prokhorov (GHP) topology on the space of trees.
- Significance: This allows the derivation of scaling limits for trees by proving the functional convergence of their encoding processes under the $M_1$ topology, even when the limits are discontinuous.

B. Combinatorial Analysis of Rotation

To study $\text{Rot}(T_n)$ , the author analyzes the relationship between the encoding processes of the original tree $T_n$ and the rotated tree $\text{Rot}(T_n)$ .

Internal Subtree: The author defines $(\text{Rot } T)^\circ$ as the subtree of internal vertices of the rotated tree.
Mirror Transformation: A key tool is the mirror tree $T^\div$ , obtained by reversing the order of children. The paper establishes a link between the Łukasiewicz walk of $T_n$ and the height of the internal subtree of $\text{Rot}(T_n)$ via the mirror tree.
Height Formula: A crucial combinatorial identity relates the height of a vertex $u$ in $T_n$ to the height of its rotated counterpart $e_u$ in $(\text{Rot } T_n)^\circ$ :
$|e_u| = |u| - 1 + L(u)$
where $L(u)$ is the number of edges grafted to the left of the ancestral spine of $u$ .
M1 Distance Control: The author constructs specific parametric representations to show that the rescaled height and contour processes of $\text{Rot}(T_n)$ are close to those of $T_n$ (or its mirror) in the $M_1$ metric, despite having different jump structures.

3. Key Contributions and Results

A. Theoretical Framework

Proposition 1.1 & 1.2: Proves the continuity of the map $x \mapsto T_x$ and $x \mapsto (T_x, \mu_x)$ from the space of càdlàg functions (with $M_1$ topology) to the space of $\mathbb{R}$ -trees (with GHP topology). This generalizes the classical result for continuous functions.
Proposition 1.4: Characterizes the limit tree $T_x$ encoded by an $\alpha$ -stable excursion ( $\alpha \in (1, 2)$ ). It is shown to be a binary tree (max degree 3) where the measure is supported entirely on the leaves. This contrasts with the stable tree $T_h$ (limit of $T_n$ ), which has vertices of infinite degree.

B. Scaling Limits of Rotated Trees (The Main Theorem)

The paper establishes the joint scaling limits of $(T_n, \text{Rot } T_n)$ for critical BGW trees attracted to a stable law of index $\alpha \in (1, 2]$ .

Case 1: Finite Variance ( $\alpha = 2$ )

Result: The rotation acts as a dilation.
$\left( \frac{1}{\sqrt{n}} T_n, \frac{1}{\sqrt{n}} \text{Rot } T_n \right) \xrightarrow{d} \left( \frac{2}{\sigma} T_e, \frac{2+\sigma^2}{\sigma} T_e \right)$
where $T_e$ is the Brownian CRT. The limit tree is the same as the original, just scaled by a factor of $1 + \sigma^2/2$.

Case 2: Infinite Variance ( $\alpha \in (1, 2)$ )

Result: The rotation changes the geometry of the tree. The limit is not a dilation of the original stable tree.
$\left( \frac{\ell(n)}{n^{1-1/\alpha}} T_n, \frac{1}{\ell(n)n^{1/\alpha}} \text{Rot } T_n \right) \xrightarrow{d} (T_h, T_x)$
- $T_h$ : The standard $\alpha$ -stable tree (encoded by the continuous height process $h$ ).
- $T_x$ : A new family of random $\mathbb{R}$ -trees encoded by the càdlàg excursion $x$ of the spectrally positive $\alpha$ -stable Lévy process.
Geometric Differences:
- Hausdorff Dimension: $\dim_H(T_h) = \frac{\alpha}{\alpha-1}$ , whereas $\dim_H(T_x) = \alpha$ .
- Structure: $T_x$ is binary; $T_h$ has infinite degree vertices.
- Relation to Looptrees: $T_x$ is identified as a spanning R-tree of the stable looptree $L_x$ (introduced by Curien & Kortchemski).

C. Co-rotation and Duality

The paper also studies the co-rotation ( $\text{Tor}$ ), a symmetric counterpart to rotation.

Surprising Result: While $\text{Rot}(T_n)$ $Rot (T_{n})$ and $\text{Tor}(T_n)$ $Tor (T_{n})$ have the same distributional scaling limit (both converge to $T_x$ $T_{x}$ ), their Łukasiewicz walks behave differently.
- The Łukasiewicz walk of $\text{Tor}(T_n)$ converges to the same limit as $T_n$ (the stable excursion $x$ ).
- The Łukasiewicz walk of $\text{Rot}(T_n)$ converges to the continuous height process $h$ .
This highlights that different encoding processes can converge to different limits even if the trees themselves converge to the same distribution, and vice versa.

4. Significance

Resolution of a Conjecture: The paper definitively answers whether the "rotation as dilation" property holds for general stable trees. It shows that while true for the Gaussian case ( $\alpha=2$ ), it fails for the stable case ( $\alpha < 2$ ), revealing a new class of random trees ( $T_x$ ).
Methodological Advancement: By rigorously establishing the continuity of the tree-coding map under the Skorokhod $M_1$ topology, the paper provides a robust framework for studying scaling limits of discrete structures that converge to discontinuous processes. This is crucial for problems involving jumps, which are common in stable processes but difficult to handle with the standard $J_1$ topology.
Connection to Looptrees: The identification of the limit tree $T_x$ as a spanning tree of the stable looptree $L_x$ bridges the gap between two major objects in the theory of random trees: stable trees and stable looptrees. It provides a geometric interpretation of the rotation operation in the continuum limit.
Geometric Insight: The results demonstrate that combinatorial operations like rotation can fundamentally alter the fractal geometry (Hausdorff dimension) and topological structure (degree distribution) of random trees in the infinite variance regime.

In summary, the paper extends the theory of random tree scaling limits to discontinuous encodings, proving that the rotation of critical stable trees yields a distinct, binary, lower-dimensional random tree structure, fundamentally different from the original stable tree.

Rotating random trees with Skorokhod's M1M_1M1​ topology