arxiv: 2605.07664 · v1 · submitted 2026-05-08 · 🧮 math.CO

Recognition: no theorem link

Benjamini-Schramm convergence and subtrees of trees

Stijn Cambie , Stephan Wagner , Ruoyu Wang

Authors on Pith no claims yet

Pith reviewed 2026-05-11 02:03 UTC · model grok-4.3

classification 🧮 math.CO

keywords Benjamini-Schramm convergencesubtree entropysubtree densitylocal weak convergencetreesasymptoticsseries-reduced trees

0 comments

The pith

For a Benjamini-Schramm convergent sequence of trees, the subtree entropy converges to a constant fixed by the limiting object.

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

The paper studies how subtree counts behave in sequences of trees whose local neighborhoods stabilize. It proves that the normalized log of the total number of subtrees converges to a number that depends only on the Benjamini-Schramm limit. The probability that a random vertex lies in a random subtree also converges, once the limit is required to contain no arbitrarily long paths. These limits turn global counting quantities into functionals of local structure alone. The attainable values of both quantities are moreover dense in the unit interval for ordinary trees and for series-reduced trees.

Core claim

In a Benjamini-Schramm-convergent sequence of trees the subtree entropy, the logarithm of the number of subtrees divided by the order, converges to a constant determined solely by the limit. The subtree density, the probability that a uniformly random vertex belongs to a uniformly random subtree, converges under the further restriction that the limit contains no infinite or arbitrarily long paths. The paper also shows that both the subtree density and the average subtree entropy are dense in [0,1] for sequences of general trees and for sequences of series-reduced trees.

What carries the argument

Benjamini-Schramm convergence (local weak convergence), which encodes the distribution of neighborhoods around a typical vertex and thereby converts global subtree enumeration into a functional of the limiting probability space on rooted trees.

If this is right

Subtree entropy becomes a continuous functional on the space of rooted trees equipped with local weak topology.
The limit of subtree density exists and equals an explicit functional of the local limit once paths are bounded.
The set of possible limiting subtree entropies is dense in [0,1] already for ordinary trees.
The same density holds when the trees are restricted to be series-reduced.

Where Pith is reading between the lines

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

Large trees sampled from the same local limit will exhibit essentially identical subtree statistics regardless of their global realizations.
The convergence supplies a way to predict the complexity of subtree-enumeration tasks on tree-like networks from local degree and branching data alone.
Similar arguments may apply to other additive or multiplicative subtree functionals once suitable local limits are imposed.

Load-bearing premise

The sequence of trees must converge locally weakly around a random vertex, and for the density result the limiting object must contain no arbitrarily long paths.

What would settle it

A Benjamini-Schramm convergent sequence of trees in which the subtree count per vertex oscillates and fails to approach any single limit.

Figures

Figures reproduced from arXiv: 2605.07664 by Ruoyu Wang, Stephan Wagner, Stijn Cambie.

**Figure 1.** Figure 1: The subtree core c lies in the branch T1 of v1. 3 Number of subtrees and Benjamini–Schramm convergence 3.1 Proof of Theorem 1 We start the proof of our first main theorem with two more auxiliary lemmas. Lemma 4. Let T be a tree of order n, and let c be a subtree core of T. Then |log(1 + N(T, c)) − log N(T)| ≤ log 2. Proof. Theorem 6 in [24] (see also [23, Theorem 5]) states, rewritten in our notation, that… view at source ↗

**Figure 2.** Figure 2: C1, C2 and C3. Regular trees (Bethe trees). As a more complicated example, let us consider the sequence of 3-regular trees RT 3 n , shown in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: First four trees in the sequence RT 3 n , with dashed lines indicating the sets L 0 n . 8 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

**Figure 4.** Figure 4: RT3 is the infinite canopy tree. On the other hand, one can obtain the explicit formula N(RT3 n ) = (1 + mn−1) 3 + nX−1 k=0 3 · 2 n−k−1mk. The first term stands for the number of subtrees of RT 3 n containing the centre (making use of (2) again), while the k-th term in the sum is the number of subtrees where the innermost vertex belongs to L k n . In view of the rapid growth of the sequence mk, the first t… view at source ↗

**Figure 5.** Figure 5: The construction in the proof of Proposition 17. [PITH_FULL_IMAGE:figures/full_fig_p023_5.png] view at source ↗

read the original abstract

In this paper, we study the asymptotic behaviour of the number of subtrees and the subtree density for a sequence of trees that converges in the Benjamini-Schramm sense. Benjamini-Schramm convergence, also called local weak convergence, describes the local behaviour of a sequence of graphs. Here we show that for a Benjamini-Schramm-convergent sequence of trees, the subtree entropy, i.e., the logarithm of the number of subtrees divided by the order, converges to a constant depending only on the limit. The same holds true for the subtree density, i.e., the probability of a uniformly random vertex being contained in a uniformly random subtree, provided that long paths are ruled out in the limit. Related to this, we show that the subtree density and the average subtree entropy are dense in different parts of the unit interval $[0,1]$ for both general trees and series-reduced trees.

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

Subtree entropy and density converge to limit-dependent constants under Benjamini-Schramm convergence for trees, via recursive decompositions that yield a continuous functional on unimodular random trees.

read the letter

The key point is that for a Benjamini-Schramm convergent sequence of trees, the normalized log number of subtrees converges to a value fixed by the local limit. The subtree density converges too, but only after excluding sequences whose limit contains long paths. They prove the path condition is necessary with an explicit counterexample of paths themselves. This is the main new content: extending local weak convergence to these particular global counting invariants on trees. The approach works by writing subtree counts through recursive decompositions on rooted trees, showing those quantities are measurable with respect to the limit, and verifying that the map from the space of unimodular random trees to the entropy or density is continuous in the Benjamini-Schramm topology. Uniform integrability handles the density case once long paths are ruled out. They also establish that both quantities are dense in [0,1] for ordinary trees and for series-reduced trees. The recursive decomposition fits the structure of trees naturally and avoids circularity. The continuity argument and the counterexample give the claims a solid footing. The only minor softness is that the density-in-[0,1] statements for series-reduced trees feel like a modest extension of the general-tree case rather than an independent advance, though they are still worth recording. No load-bearing gaps appear in the logic or the handling of measurability. This paper is for people working on graph limits, local convergence, and enumeration problems in trees or random structures. A reader who already knows Benjamini-Schramm convergence and wants to see how it controls subtree statistics will get direct value. It is narrow but technically clean, so it deserves a serious referee who can check the details of the functional continuity and the uniform-integrability step. I would send it to peer review.

Referee Report

1 major / 3 minor

Summary. The manuscript establishes convergence results for subtree entropy and subtree density in sequences of trees that converge in the Benjamini-Schramm topology. Specifically, the normalized logarithm of the number of subtrees converges to a functional of the limiting unimodular random tree, and a similar result holds for the density under the assumption that the limit contains no infinite paths. Additionally, the possible values of these quantities are shown to be dense in [0,1] for both general and series-reduced trees.

Significance. This work bridges local convergence with global combinatorial invariants on trees. The use of recursive decompositions to express subtree counts in a measurable way with respect to the local weak limit, and proving continuity of the resulting functional, provides a template for similar extensions. The counterexample showing necessity of the no-long-paths condition is valuable. The density results indicate that these invariants can take a wide range of values.

major comments (1)

The central claim in the main convergence theorem for subtree entropy relies on expressing subtree counts via recursive decompositions that are measurable w.r.t. the local weak limit and showing the functional is continuous in the BS topology; an explicit verification that the decomposition preserves the required measurability (e.g., with respect to the sigma-algebra of rooted neighborhoods) would confirm there are no hidden measurability gaps.

minor comments (3)

The definition of subtree entropy (log of subtree count divided by order) and subtree density should be restated uniformly in the introduction and in the statements of the main theorems to avoid any ambiguity in notation.
The paper would benefit from a brief comparison in the introduction to prior results on BS convergence for trees (e.g., those involving other global functionals like matching numbers) to better situate the contribution.
In the section establishing density in [0,1], the constructions for series-reduced trees could include a short remark on why the same density holds as for general trees, to improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We are grateful to the referee for the careful reading and positive assessment of the manuscript, including the recommendation for minor revision. We respond to the single major comment below.

read point-by-point responses

Referee: The central claim in the main convergence theorem for subtree entropy relies on expressing subtree counts via recursive decompositions that are measurable w.r.t. the local weak limit and showing the functional is continuous in the BS topology; an explicit verification that the decomposition preserves the required measurability (e.g., with respect to the sigma-algebra of rooted neighborhoods) would confirm there are no hidden measurability gaps.

Authors: We agree that an explicit verification would improve clarity and confirm the absence of measurability issues. In the revised manuscript, we will insert a short additional paragraph (or lemma) immediately following the definition of the recursive decomposition. This paragraph will explicitly construct the measurable functions on the space of rooted neighborhoods that encode the subtree-count recursion, verify that these functions are invariant under the equivalence relation of the Benjamini-Schramm topology, and confirm that the resulting functional is measurable with respect to the sigma-algebra generated by finite rooted neighborhoods. revision: yes

Circularity Check

0 steps flagged

No significant circularity; convergence follows from continuity of measurable functionals under BS topology

full rationale

The central claims establish convergence of subtree entropy (log of subtree count normalized by order) and subtree density for BS-convergent tree sequences by expressing these quantities via recursive decompositions on rooted trees that are measurable with respect to the local weak limit. The resulting functionals are shown to be continuous in the Benjamini-Schramm topology, with uniform integrability obtained by excluding infinite/arbitrarily long paths in the limit (and necessity demonstrated by a counterexample sequence of paths). These steps rely on the external definition of local weak convergence and standard properties of unimodular random trees, without any reduction of the target quantities to fitted parameters, self-definitions, or load-bearing self-citations. The density results in [0,1] are obtained via explicit constructions of convergent sequences, which are independent of the main convergence theorem.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Claims rest on the standard definition of Benjamini-Schramm convergence for rooted graphs and basic facts about finite trees and their connected subgraphs; no free parameters or new entities are introduced.

axioms (2)

domain assumption Benjamini-Schramm convergence is defined and well-behaved for sequences of finite trees
The paper invokes the standard local weak convergence notion for graphs to obtain the stated limits.
standard math A subtree is a connected acyclic subgraph of a tree
Basic combinatorial definition used throughout the counting arguments.

pith-pipeline@v0.9.0 · 5452 in / 1349 out tokens · 62377 ms · 2026-05-11T02:03:41.535479+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

[1]

MatchingsinBenjamini-Schrammconvergent graph sequences.Trans

M.Abért, P.Csikvári, P.E.Frenkel, andG.Kun. MatchingsinBenjamini-Schrammconvergent graph sequences.Trans. Amer. Math. Soc., 368(6):4197–4218, 2016

work page 2016
[2]

Abért, P

M. Abért, P. Csikvári, and T. Hubai. Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy.J. Stat. Phys., 161(1):16–34, 2015

work page 2015
[3]

Abért and T

M. Abért and T. Hubai. Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs.Combinatorica, 35(2):127–151, 2015

work page 2015
[4]

Benjamini-Schrammconvergenceandpointwiseconvergence of the spectral measure.Preprint, 2013

M.Abért, A.Thom, andB.Virág. Benjamini-Schrammconvergenceandpointwiseconvergence of the spectral measure.Preprint, 2013

work page 2013
[5]

A. V. Aho and N. J. A. Sloane. Some doubly exponential sequences.Fibonacci Quart., 11(4):429–437, 1973

work page 1973
[6]

E. O. D. Andriantiana, S. Wagner, and H. Wang. Greedy trees, subtrees and antichains. Electron. J. Combin., 20(3):Paper 28, 25, 2013

work page 2013
[7]

E. O. D. Andriantiana, S. Wagner, and H. Wang. Extremal problems for trees with given segment sequence.Discrete Appl. Math., 220:20–34, 2017

work page 2017
[8]

Benjamini and O

I. Benjamini and O. Schramm. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab., 6:no. 23, 13, 2001

work page 2001
[9]

X. S. Cai and S. Janson. Non-fringe subtrees in conditioned Galton-Watson trees.Electron. J. Combin., 25(3):Paper No. 3.40, 30, 2018

work page 2018
[10]

Cambie and S

S. Cambie and S. Wagner. Mean subtree order under contraction.Preprint, 2026

work page 2026
[11]

Cambie, S

S. Cambie, S. Wagner, and H. Wang. On the maximum mean subtree order of trees.European J. Combin., 97:Paper No. 103388, 19, 2021

work page 2021
[12]

Csikvári and P

P. Csikvári and P. E. Frenkel. Benjamini-Schramm continuity of root moments of graph polynomials.European J. Combin., 52:302–320, 2016. 23

work page 2016
[13]

Haslegrave

J. Haslegrave. Extremal results on average subtree density of series-reduced trees.J. Combin. Theory Ser. B, 107:26–41, 2014

work page 2014
[14]

R. E. Jamison. On the average number of nodes in a subtree of a tree.J. Combin. Theory Ser. B, 35(3):207–223, 1983

work page 1983
[15]

Kirk and H

R. Kirk and H. Wang. Largest number of subtrees of trees with a given maximum degree. SIAM J. Discrete Math., 22(3):985–995, 2008

work page 2008
[16]

R. Lyons. Asymptotic enumeration of spanning trees.Combin. Probab. Comput., 14(4):491– 522, 2005

work page 2005
[17]

Mol and O

L. Mol and O. R. Oellermann. Maximizing the mean subtree order.J. Graph Theory, 91(4):326–352, 2019

work page 2019
[18]

The On-Line Encyclopedia of Integer Sequences, 2026

OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2026. Published electronically athttps://oeis.org

work page 2026
[19]

Ralaivaosaona and S

D. Ralaivaosaona and S. Wagner. On the distribution of subtree orders of a tree.Ars Math. Contemp., 14(1):129–156, 2018

work page 2018
[20]

Ralaivaosaona and S

D. Ralaivaosaona and S. Wagner. A central limit theorem for additive functionals of increasing trees.Combin. Probab. Comput., 28(4):618–637, 2019

work page 2019
[21]

A. V. Sills and H. Wang. The minimal number of subtrees of a tree.Graphs Combin., 31(1):255–264, 2015

work page 2015
[22]

L. A. Székely and H. Wang. On subtrees of trees.Adv. in Appl. Math., 34(1):138–155, 2005

work page 2005
[23]

L. A. Székely and H. Wang. Extremal values of ratios: distance problems vs. subtree problems in trees.Electron. J. Combin., 20(1):Paper 67, 20, 2013

work page 2013
[24]

L. A. Székely and H. Wang. Extremal values of ratios: distance problems vs. subtree problems in trees II.Discrete Math., 322:36–47, 2014

work page 2014
[25]

Vince and H

A. Vince and H. Wang. The average order of a subtree of a tree.J. Combin. Theory Ser. B, 100(2):161–170, 2010

work page 2010
[26]

S. Wagner. Central limit theorems for additive tree parameters with small toll functions. Combin. Probab. Comput., 24(1):329–353, 2015

work page 2015
[27]

Y. Yang, H. Liu, and H. Wang. Subtrees, BC-subtrees of generalized Bethe trees and related questions.Ars Combin., 121:47–63, 2015

work page 2015
[28]

Zhang and X.-D

X.-M. Zhang and X.-D. Zhang. The minimal number of subtrees with a given degree sequence. Graphs Combin., 31(1):309–318, 2015. 24

work page 2015