A counter-example to persistence in generalised preferential attachment trees
Pith reviewed 2026-05-10 10:01 UTC · model grok-4.3
The pith
A minor modification of an earlier construction produces a valid generalized preferential attachment tree where sum 1/f(j)^2 converges yet no node remains the unique maximum-degree vertex for all large times.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We exhibit an attachment function f for which sum 1/f(j)^2 < ∞ but the associated random tree has no persistent hub: at arbitrarily late times there are at least two vertices of maximal degree. The example is obtained from the Galganov-Ilienko counter-example by a minor alteration that preserves the preferential-attachment dynamics yet removes the persistence property.
What carries the argument
A random recursive tree grown by attaching each new vertex to an existing vertex v with probability proportional to f(deg(v)), where f is chosen so that the square-summability condition holds but the degree process never settles on a unique leader.
If this is right
- The square-summability condition on f is insufficient to guarantee persistence of the maximum degree.
- Any proof of persistence in these models must impose a strictly stronger restriction on the growth of f.
- Counter-examples of the same style can be constructed for other summability regimes or for models with multiple attachment functions.
- The long-term degree distribution may remain non-degenerate even when the sum condition holds.
Where Pith is reading between the lines
- The precise threshold on f separating persistent-hub and non-persistent regimes remains open and may involve slower-than-square decay.
- Similar modifications could be applied to preferential attachment graphs with cycles or to models with fitness variables.
- Numerical simulation of the constructed f for moderate n would give immediate visual confirmation that multiple high-degree vertices coexist for long periods.
Load-bearing premise
The minor modification of the Galganov-Ilienko construction produces a valid generalised preferential attachment process with the chosen f yet still lacks a persistent hub.
What would settle it
An explicit verification that the modified attachment probabilities satisfy the preferential-attachment rule at every step, that sum 1/f(j)^2 converges, and that the resulting degree sequence has at least two vertices of record degree at infinitely many times.
read the original abstract
Consider a generalised preferential attachment tree with attachment function $f$, that is a random tree, where at each time-step a node connects to an existing node $v$ with probability proportional to $f(\mathrm{deg}(v))$, where $\mathrm{deg}(v)$ denotes the degree of the node in the existing tree. We provide a counter-example to a conjecture of the author asserting that under the assumption $\sum_{j=1}^{\infty} \frac{1}{f(j)^2} < \infty$ there is a persistent hub in the model, that is, a single node that has the maximal degree for all but finitely many time-steps. The counter-example is a minor modification of a related counter-example due to Galganov and Ilienko.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims to provide a counter-example to the conjecture that the condition ∑_{j=1}^∞ 1/f(j)^2 < ∞ guarantees a persistent hub (a node of maximal degree for all but finitely many steps) in a generalised preferential attachment tree, where new nodes attach to existing node v with probability proportional to f(deg(v)). The counter-example is obtained via a minor modification of the Galganov-Ilienko construction.
Significance. If the modified construction is shown to be a valid generalised preferential attachment process for an f satisfying the summability condition while having no persistent hub, the result is significant: it demonstrates that the summability condition is insufficient for persistence and refines the known criteria for hub formation in preferential attachment models. The paper's direct falsification via construction is a strength.
major comments (1)
- The central claim rests on the assertion that a minor modification of the Galganov-Ilienko construction yields a process whose attachment probabilities are exactly proportional to f(deg(v)) for the chosen f (satisfying ∑ 1/f(j)^2 < ∞) while the degree sequence has no node that is maximal for all but finitely many times. The manuscript does not supply an explicit verification of this preservation of the attachment kernel or of the absence of persistence; without it the counter-example is not confirmed. This is load-bearing for the main result.
minor comments (1)
- [Abstract] The abstract states the existence of the counter-example but provides no outline of the modification; adding one or two sentences would improve accessibility without lengthening the paper.
Simulated Author's Rebuttal
We appreciate the referee's detailed comments and recommendation for major revision. Below we respond to the major comment and outline the changes we will make to the manuscript.
read point-by-point responses
-
Referee: The central claim rests on the assertion that a minor modification of the Galganov-Ilienko construction yields a process whose attachment probabilities are exactly proportional to f(deg(v)) for the chosen f (satisfying ∑ 1/f(j)^2 < ∞) while the degree sequence has no node that is maximal for all but finitely many times. The manuscript does not supply an explicit verification of this preservation of the attachment kernel or of the absence of persistence; without it the counter-example is not confirmed. This is load-bearing for the main result.
Authors: We acknowledge that the current version of the manuscript lacks an explicit, self-contained verification of the key properties of the modified construction. To address this, we will revise the paper by including a new section that provides a detailed proof. Specifically, we will verify that the minor modifications to the Galganov-Ilienko construction maintain the exact proportionality of attachment probabilities to f(deg(v)) for the chosen f satisfying the summability condition, and we will demonstrate rigorously that no node remains the unique maximum-degree node for all but finitely many steps. This addition will confirm the validity of the counter-example. revision: yes
Circularity Check
Direct construction falsifies conjecture without self-referential reduction
full rationale
The paper supplies an explicit counter-example via a minor modification of the Galganov-Ilienko construction. The attachment rule is stated directly as probability proportional to f(deg(v)), the summability condition on f is imposed by choice of sequence, and the absence of a persistent hub is verified by analyzing the modified degree process. No quantity is defined in terms of another that it is supposed to derive; no parameter is fitted to data and then relabeled a prediction; the central claim does not rest on a self-citation whose content is itself unverified or on an ansatz imported from prior work by the same authors. The fact that the refuted conjecture originated with the present author is irrelevant to circularity, because the counter-example is constructed and argued independently of that conjecture.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard axioms of probability and the definition of the generalised preferential attachment process via the attachment function f.
Reference graph
Works this paper leans on
-
[1]
S. Banerjee and S. Bhamidi. Persistence of hubs in growing random networks.Probab. Theory Related Fields, 180(3-4):891–953, 2021
work page 2021
-
[2]
S. Dereich and P. M¨ orters. Random networks with sublinear preferential attachment: degree evolutions.Electron. J. Probab., 14:no. 43, 1222–1267, 2009
work page 2009
- [3]
-
[4]
O. Galganov and A. Ilienko. Explosion and non-explosion in pure birth Crump–Mode–Jagers branching processes. arXiv preprint arXiv:2601.06850, 2026
- [5]
- [6]
-
[7]
T. Iyer and B. Lodewijks. On the structure of genealogical trees associated with explosive Crump- Mode-Jagers branching processes. arXiv preprint arXiv:2311:14664, 2023
work page 2023
- [8]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.