Asymptotic height of Plancherel random trees

Shengjun Zhang

arxiv: 2604.25877 · v1 · submitted 2026-04-28 · 🧮 math.PR · math.CO

Asymptotic height of Plancherel random trees

Shengjun Zhang This is my paper

Pith reviewed 2026-05-07 15:07 UTC · model grok-4.3

classification 🧮 math.PR math.CO

keywords Plancherel random treestree height asymptoticsEwens fragmentationbranching random walkPoisson-Dirichlet distributionvariational principle

0 comments

The pith

Plancherel random trees with n vertices have height H_n such that H_n over log n converges in probability to an explicit constant c star of 2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper investigates the maximum height in a random rooted tree chosen from a Plancherel-type probability measure on trees with n vertices. It introduces a one-parameter family of analogous random trees indexed by theta greater than zero and establishes that their height divided by log n converges in probability to an explicit constant depending on theta. The classical Plancherel case corresponds to the value theta equals 2. The argument proceeds by identifying the trees with Ewens fragmentation processes and deriving matching upper and lower bounds through s-mass functionals together with an embedding into a branching random walk whose displacements are governed by a Poisson-Dirichlet distribution.

Core claim

For the family of random trees T_n of theta, the height H_n satisfies that H_n over log n converges in probability to the constant c star of theta. In the Plancherel case theta equals 2 this yields the precise asymptotic growth rate. The constant itself is characterized by a variational principle attached to the branching random walk with logarithmic displacements that arises from the Poisson-Dirichlet process.

What carries the argument

The embedding of Ewens fragmentation trees into a branching random walk whose steps are logarithmic displacements drawn from a Poisson-Dirichlet distribution.

Load-bearing premise

Plancherel random trees can be identified with Ewens fragmentation trees that exhibit a sharp threshold phenomenon for their height.

What would settle it

Direct simulation of Plancherel random trees for n on the order of one million or larger, followed by checking whether the observed ratio of height to log n stabilizes near the predicted numerical value of c star of 2.

Figures

Figures reproduced from arXiv: 2604.25877 by Shengjun Zhang.

**Figure 1.** Figure 1: Plancherel tree of size 3000. Theorem 1.5 (Convergence of the scaled height). There exists a constant c > 0 such that Hn log n P −−−→ n→∞ c . The value of the constant c is inf t>1 t − log βt(2) ≈ 1.6738, with βt(2) = Γ(t) Γ(3) Γ(2 + t) = 2 t(t + 1) view at source ↗

**Figure 2.** Figure 2: Graph of − κ(t) t and −κ ′ (t) for θ = 2; t⋆ ≈ 2.9207 and v⋆ ≈ 0.5974. Lemma 5.12. Recall that κ(t) = log Γ(t) + log Γ(θ + 1) − log Γ(θ + t) and v⋆ = supt>1 (− κ(t) t ). There exists ε0 > 0 such that for every a ∈ (v⋆, v⋆ + ε0), there exists a unique t ∈ (1, ∞) satisfying a = −κ ′ (t). Proof. Set g(t) := −κ ′ (t) = ψ(θ + t) − ψ(t), t > 1, view at source ↗

**Figure 3.** Figure 3: The first four generations of a cemetery-extended tree. The distinguished spine (Uh)h≥0 is highlighted in red, while cemetery children are shown in gray dashed style. We recall from Subsection 1.5 the definition of the spinal space: Ω sp := n ( eT , K,(Uh)h≥0) ∈ Ωe × UN : U0 = ∅, Uh+1 is a child of Uh, ∀h ≥ 0 o view at source ↗

read the original abstract

We study a natural analogue of Ulam's problem for random rooted trees distributed according to a Plancherel-type measure. This probability measure is closely related to the classical Plancherel measure on integer partitions. For a Plancherel random tree $T_n$ with $n$ vertices, we investigate the asymptotic behavior of its height $H_n$, defined as the maximal distance from the root to a leaf. We prove that this height grows logarithmically. More precisely, there is a one-parameter family of random trees $(T_n(\theta))_{n \in \mathbb{N}}$ indexed by $\theta>0$ such that $\frac{H_n}{\log n}$ converges in probability to $c_\star(\theta)$, where $c_\star(\theta)$ is an explicit constant depending on the parameter $\theta$. The case of Plancherel trees corresponds to the parameter $\theta=2$. The proof is based on the fact that the Plancherel random trees can be viewed as Ewens fragmentation trees, for which the height exhibits a sharp threshold phenomenon. An upper bound is obtained via $s$-mass functionals and contraction estimates, while the lower bound is derived by embedding the model into a branching random walk with logarithmic displacements governed by a Poisson--Dirichlet distribution. The constant $c_\star(\theta)$ is characterized through a variational principle associated with this branching random walk.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Plancherel random trees have height asymptotic to c log n in probability, with the constant from a variational problem on a Poisson-Dirichlet branching random walk.

read the letter

The main thing to know is that this paper pins down the height of Plancherel random trees as growing like c log n in probability, where c is an explicit variational constant tied to a branching random walk with Poisson-Dirichlet(2) increments. It also sets up a one-parameter family of trees indexed by θ that covers the Plancherel case at θ=2. This is the first such logarithmic asymptotics for the model. The proof reduces the trees to Ewens fragmentation trees at θ=2 via the RSK correspondence and the cycle structure of the associated permutations. From there the upper bound comes from s-mass contraction estimates, the lower bound from embedding the log-mass process into the branching random walk, and the constant from the standard large-deviation analysis of the maximum in that walk. The steps line up without circularity once the fragmentation representation is in place, and they rest on known facts about Poisson-Dirichlet processes and fragmentation trees. The argument is direct and uses the right tools for the job. One soft spot is that the constant stays in variational form without a closed expression or numerical value, so immediate simulation checks are harder than they could be. That does not affect the asymptotic claim, but it does leave the result somewhat abstract until the constant is evaluated. The convergence is only in probability, which is enough for what is claimed but leaves stronger modes open. This paper is for people already working in probabilistic combinatorics, random partitions, and fragmentation processes. A reader focused on height asymptotics for random trees or extensions of Ulam's problem will get concrete value from the embedding technique. It deserves a serious referee because the central argument holds up, the result is new, and the claims are checkable against prior work on these objects. I would send it to peer review.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that the height H_n of Plancherel random trees T_n on n vertices satisfies H_n / log n converging in probability to an explicit constant c_*(2). The result is obtained by identifying the Plancherel measure with Ewens fragmentation trees at parameter θ=2 (Section 2), deriving the limsup via s-mass contraction estimates (Lemma 3.4), and the liminf via embedding the log-mass process into a branching random walk whose displacements follow the Poisson-Dirichlet(2) law (Proposition 4.1), with the limiting constant characterized by a variational principle on the BRW maximum (Theorem 5.2).

Significance. If the central claims hold, the paper resolves the logarithmic height asymptotics for Plancherel random trees, furnishing an explicit constant via a variational principle that extends Ulam's problem to this measure. The embedding into a BRW with Poisson-Dirichlet displacements and the resulting variational characterization constitute a clear methodological strength, as they rely on established properties of the PD process and yield a falsifiable, computable limit.

minor comments (2)

[Introduction] Introduction: the one-parameter family T_n(θ) is introduced only in the abstract and main theorem; a self-contained definition via the Ewens sampling formula or the associated fragmentation process should appear before the statement of the result.
[Theorem 5.2] Theorem 5.2: while the variational principle for the BRW maximum is standard, the explicit form of the rate function induced by the Poisson-Dirichlet(2) displacement law is not recalled; adding the relevant expression would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, recognition of its methodological contributions, and recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper proves the Plancherel-Ewens correspondence independently in Section 2 via RSK and permutation cycles. Upper bound uses s-mass contraction (Lemma 3.4) and lower bound embeds into BRW with PD(2) increments (Prop. 4.1), then applies standard large-deviation analysis (Thm. 5.2) for the variational constant c_*(θ). All steps rely on external properties of Poisson-Dirichlet processes and fragmentation trees; no step reduces by definition, fit, or self-citation chain to the target height limit. The result is not forced by its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the domain assumption that Plancherel trees coincide with Ewens fragmentation trees and that the height process admits a sharp threshold under the Poisson-Dirichlet displacements; no free parameters are fitted inside the derivation itself, and no new entities are postulated.

axioms (2)

domain assumption Plancherel random trees can be viewed as Ewens fragmentation trees
Invoked to transfer the height analysis to the fragmentation setting where sharp thresholds are known.
domain assumption The height process under the Poisson-Dirichlet branching random walk admits a variational characterization for its speed
Used to obtain the explicit constant c_star(θ).

pith-pipeline@v0.9.0 · 5538 in / 1448 out tokens · 47737 ms · 2026-05-07T15:07:27.620991+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

[1]

Okounkov

[Oko00] A. Okounkov. Random matrices and random permutations.Intern. Math. Res. Notices, 2000(20):1043– 1095,

work page 2000
[2]

[Pit06] J. Pitman. Combinatorial stochastic processes. InÉcole d’été de probabilités de Saint-Flour XXXII, 2002, volume 1875 ofLecture Notes in Mathematics. Springer,

work page 2002
[3]

Shi.Branching Random Walks - École d’été de probabilités de Saint-Flour XLII - 2012, volume 2151 of Lecture Notes in Mathematics

[Shi15] Z. Shi.Branching Random Walks - École d’été de probabilités de Saint-Flour XLII - 2012, volume 2151 of Lecture Notes in Mathematics. Springer,

work page 2012
[4]

[Wat74] G. A. Watterson. The sampling theory of selectively neutral alleles.Advances in Applied Probability, 6(3):463–488, 1974

work page 1974

[1] [1]

Okounkov

[Oko00] A. Okounkov. Random matrices and random permutations.Intern. Math. Res. Notices, 2000(20):1043– 1095,

work page 2000

[2] [2]

[Pit06] J. Pitman. Combinatorial stochastic processes. InÉcole d’été de probabilités de Saint-Flour XXXII, 2002, volume 1875 ofLecture Notes in Mathematics. Springer,

work page 2002

[3] [3]

Shi.Branching Random Walks - École d’été de probabilités de Saint-Flour XLII - 2012, volume 2151 of Lecture Notes in Mathematics

[Shi15] Z. Shi.Branching Random Walks - École d’été de probabilités de Saint-Flour XLII - 2012, volume 2151 of Lecture Notes in Mathematics. Springer,

work page 2012

[4] [4]

[Wat74] G. A. Watterson. The sampling theory of selectively neutral alleles.Advances in Applied Probability, 6(3):463–488, 1974

work page 1974