pith. sign in

arxiv: 2602.14741 · v2 · pith:3VPS5AOWnew · submitted 2026-02-16 · 🧮 math.PR

Partial orders and monotonicity of logarithmic depth and height in preferential attachment trees

Christian M\"onch This is my paper

Pith reviewed 2026-05-22 11:50 UTC · model grok-4.3

classification 🧮 math.PR MSC 60J8005C80
keywords preferential attachmentmonotonicitylogarithmic depthtree heightbranching processesgrowth ratio dominancepartial ordersattachment functions
0
0 comments X

The pith

The logarithmic constants for insertion depth and tree height in preferential attachment trees are monotone under profile-order assumptions on attachment functions.

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

The paper examines whether stronger preferential attachment to high-degree vertices produces shallower trees, as measured by the constants in the logarithmic growth of insertion depth and tree height. Growth-ratio dominance on attachment functions is the obvious candidate for an order that would make this intuition precise, but the authors exhibit a counterexample where this order alone does not deliver monotonicity of the constants. They show that an additional dual tail-order condition on the measures arising from the Crump-Mode-Jagers or branching random walk embedding is required. Under the combination of growth-ratio dominance and this profile-order condition, the constants for both depth and height decrease when the attachment function strengthens the preference for high degrees. This makes rigorous a natural monotonicity principle in the theory of random trees.

Core claim

Under growth-ratio dominance of attachment functions together with the dual tail-order condition on the associated measures from the CMJ/BRW embedding, the logarithmic constant governing the insertion depth of the newest vertex is smaller for the dominating function, and the same holds for the logarithmic constant governing the height of the tree.

What carries the argument

The profile-order assumptions, which consist of growth-ratio dominance on the attachment functions combined with a dual tail-order on the measures from the continuous-time branching process embedding.

If this is right

  • The insertion depth grows as c log n where c is monotone decreasing in the strength of preferential attachment.
  • The tree height grows as c' log n with c' likewise monotone.
  • These results apply to general attachment functions satisfying the stated partial orders.
  • The constants are determined by the embedding measures, so comparisons reduce to ordering those measures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The counterexample to growth-ratio dominance alone suggests that tail behavior of the measures plays a critical role in controlling the extremes of depth and height.
  • Similar monotonicity questions could be posed for other functionals of the tree such as the diameter.
  • Verification of the profile-order conditions for common attachment functions like linear preferential attachment would confirm applicability to standard models.

Load-bearing premise

The dual tail-order condition on the measures associated with the CMJ/BRW embedding must hold alongside growth-ratio dominance.

What would settle it

An explicit pair of attachment functions where growth-ratio dominance holds but the dual tail-order fails, and where the computed or simulated logarithmic constants violate monotonicity, would falsify the sufficiency of the combined assumptions.

read the original abstract

We study preferential attachment (PA) trees with general attachment functions. PA suggests an intuitive monotonicity: if high-degree vertices are rewarded more strongly, then the resulting tree should become shallower. We examine this principle through the constants governing two natural logarithmically growing observables, the insertion depth of the newest vertex and the height of the whole tree. Growth-ratio dominance (GRD) is the natural order on attachment functions, but we provide an explicit counterexample showing that GRD is not sufficient for either depth or height monotonicity at the level of logarithmic constants. The missing input is a dual tail-order condition on certain measures associated with the CMJ/BRW embedding of the PA tree. Under these profile-order assumptions we prove the expected monotonicity results.

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.

Referee Report

2 major / 2 minor

Summary. The manuscript studies preferential attachment trees with general attachment functions. It shows that growth-ratio dominance on attachment functions is insufficient to guarantee monotonicity of the logarithmic constants for insertion depth and tree height, via an explicit counterexample. Under the additional dual tail-order (profile-order) condition on the measures arising from the CMJ/BRW embedding of the PA tree, the expected monotonicity of these constants is proved.

Significance. If the counterexample and conditional proofs hold, the work clarifies the precise additional assumptions needed beyond growth-ratio dominance for monotonicity results in these models. The separation of the negative result (GRD alone fails) from the positive result (GRD plus dual tail-order suffices) is a clear contribution to the literature on random trees and their branching-process embeddings. The explicit counterexample and the use of the CMJ/BRW embedding to transfer orderings on measures to limiting constants are notable strengths.

major comments (2)
  1. [counterexample section] The counterexample in the section establishing that GRD is insufficient should include explicit verification that the chosen attachment functions satisfy growth-ratio dominance while violating the dual tail-order condition, and that the resulting logarithmic constants indeed fail to be monotone. Without these explicit checks the negative result risks being non-load-bearing for the central claim.
  2. [monotonicity proof] In the proof of monotonicity under the profile-order assumptions, the transfer from the ordered measures on the CMJ/BRW embedding to the monotonicity of the logarithmic depth and height constants relies on the specific form of the limiting constants; the argument should make explicit which properties of the embedding (e.g., the martingale limits or the offspring distributions) are used to preserve the order.
minor comments (2)
  1. [introduction and preliminaries] Notation for the attachment functions and the associated measures should be introduced with a single consistent table or list early in the paper to avoid repeated re-definition.
  2. [introduction] The abstract states that 'proofs exist under the stated assumptions'; the introduction should briefly indicate where in the manuscript the full proofs appear.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We are grateful for the recognition of the contribution in separating the insufficiency of growth-ratio dominance from the sufficiency of the additional dual tail-order condition. We respond to each major comment below and will incorporate the requested clarifications in the revised version.

read point-by-point responses

  1. Referee: [counterexample section] The counterexample in the section establishing that GRD is insufficient should include explicit verification that the chosen attachment functions satisfy growth-ratio dominance while violating the dual tail-order condition, and that the resulting logarithmic constants indeed fail to be monotone. Without these explicit checks the negative result risks being non-load-bearing for the central claim.

    Authors: We agree that explicit verification strengthens the negative result. In the revised manuscript we will add direct computations confirming that the chosen attachment functions satisfy growth-ratio dominance while violating the dual tail-order condition on the associated measures. We will also include explicit evaluation (or tight bounds) of the logarithmic depth and height constants under these functions to demonstrate the failure of monotonicity. This will make the counterexample fully load-bearing for the claim that GRD alone is insufficient. revision: yes

  2. Referee: [monotonicity proof] In the proof of monotonicity under the profile-order assumptions, the transfer from the ordered measures on the CMJ/BRW embedding to the monotonicity of the logarithmic depth and height constants relies on the specific form of the limiting constants; the argument should make explicit which properties of the embedding (e.g., the martingale limits or the offspring distributions) are used to preserve the order.

    Authors: We thank the referee for highlighting the need for greater transparency in the transfer argument. In the revised proof we will explicitly identify the relevant properties of the CMJ/BRW embedding: specifically, we will detail how the almost-sure convergence of the martingale limits and the structure of the offspring distributions ensure that profile-order on the measures is preserved when passing to the limiting logarithmic constants for insertion depth and tree height. This will clarify the precise mechanism by which the order is transferred. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes a conditional monotonicity result for logarithmic depth and height constants in preferential attachment trees via direct mathematical proof under profile-order assumptions on the CMJ/BRW embedding measures, together with an explicit counterexample showing that growth-ratio dominance alone is insufficient. The derivation chain consists of theorem statements, counterexample construction, and transfer of ordering properties from the embedding measures to the limiting constants; none of these steps reduce by the paper's own equations to a fitted parameter, self-referential definition, or load-bearing self-citation. The argument is self-contained against external benchmarks and does not invoke uniqueness theorems or ansatzes from prior author work in a circular manner.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard background results from the theory of preferential attachment processes and their continuous-time embeddings; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Standard properties of the continuous-time embedding of preferential attachment trees into Crump-Mode-Jagers or branching random walk processes hold.
    Invoked when the abstract refers to the CMJ/BRW embedding and the associated measures.

pith-pipeline@v0.9.0 · 5647 in / 1290 out tokens · 43229 ms · 2026-05-22T11:50:05.111858+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.