pith. sign in

arxiv: 2604.06012 · v1 · submitted 2026-04-07 · 🧮 math.PR · math.CO

Large fringe trees for random trees with given vertex degrees

Gabriel Berzunza Ojeda , Cecilia Holmgren , Svante Janson This is my paper

Pith reviewed 2026-05-10 18:56 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords fringe treesplane treesdegree sequencesPoisson convergencenormal convergenceStein's methodGalton-Watson treeslocal limit theorems
0
0 comments X

The pith

Counts of large fringe trees in random plane trees with given degrees converge to Poisson or normal distributions.

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

The paper investigates counts of fringe trees that grow in size along with the random plane tree having a prescribed degree sequence. It provides conditions for these counts to converge to Poisson distributions when their expectations remain bounded and to normal distributions when the expectations grow to infinity. This is achieved by applying and comparing four probabilistic techniques: the method of moments, Stein's method with coupling, the Cai-Devroye method, and Stein's method with exchangeable pairs. A local limit theorem for sums from sampling without replacement is also derived and may have wider applications. The convergence results are further shown to hold for conditioned critical Galton-Watson trees.

Core claim

We extend the study of fringe trees to the case where the target trees grow with the size of the random plane tree with given degree statistic. For the number of fringe trees isomorphic to a specific growing tree, sharing a given growing degree statistic, or of a specific growing size, we establish conditions for Poisson and normal convergence using four frameworks. We also provide a local limit theorem for sums of values obtained via sampling without replacement.

What carries the argument

The counts of growing fringe trees in plane trees with a fixed degree statistic, with convergence proved by comparing four distinct probabilistic methods including Stein's method variants.

If this is right

  • The subtree counts converge in distribution to Poisson when the mean is bounded.
  • The counts are asymptotically normal when the mean tends to infinity under the growth conditions.
  • A local limit theorem holds for the sums from sampling without replacement.
  • The results apply directly to conditioned critical Galton-Watson trees.

Where Pith is reading between the lines

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

  • The use of multiple methods provides robustness and explicit error bounds in some cases.
  • These techniques could potentially be applied to analyze large substructures in other models of random trees or graphs.
  • The local limit theorem offers a tool for approximating distributions in finite sampling scenarios beyond tree models.
  • This work helps clarify the typical large-scale local structure in random trees with constrained degrees.

Load-bearing premise

The random objects are plane trees with a given degree statistic and the target fringe trees grow in a manner compatible with the convergence regimes analyzed.

What would settle it

A counterexample where the count of a growing fringe tree with bounded expected value fails to converge in total variation to a Poisson distribution would falsify the claim.

read the original abstract

This paper extends the study of fringe trees in random plane trees with a given degree statistic. While previous work established the asymptotic normality of the count of fringe trees isomorphic to a fixed tree, we investigate the case where the target tree grows with the size of the random tree. We consider three primary subtree counts: the number of fringe trees isomorphic to a specific growing tree, the number of fringe trees sharing a given growing degree statistic, and the number of fringe trees of a specific growing size. To establish our results, we employ and compare four distinct probabilistic frameworks: the method of moments with the Gao-Wormald theorem, Stein's method with coupling (to provide explicit error bounds in total variation distance), the Cai-Devroye method, and Stein's method with exchangeable pairs. Our findings provide conditions for Poisson and normal convergence for these subtree counts. Additionally, we provide a local limit theorem for sums of values obtained via sampling without replacement that may be of independent interest. Finally, our results and methods are also applied to conditioned critical Galton-Watson 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.

Referee Report

0 major / 3 minor

Summary. The manuscript extends the analysis of fringe trees in random plane trees with a prescribed degree sequence to the regime where the target fringe trees grow with the host tree. It establishes conditions for Poisson and normal limits on three counts: the number of fringe trees isomorphic to a growing target, the number sharing a growing degree statistic, and the number of a given growing size. Four methods are applied in complementary regimes (moments combined with the Gao-Wormald theorem, Stein coupling for explicit total-variation bounds, the Cai-Devroye approach, and exchangeable pairs), an auxiliary local-limit theorem for sums under sampling without replacement is proved, and the results are transferred to conditioned critical Galton-Watson trees by verifying the requisite moment and growth hypotheses on the degree sequence.

Significance. If the central claims hold, the work supplies a systematic treatment of growing fringe trees, complementing earlier fixed-target results and offering explicit error bounds in one regime. The comparison of four distinct techniques across growth regimes is a methodological strength, and the sampling-without-replacement local limit theorem is likely to be of independent interest in combinatorial probability. The Galton-Watson application demonstrates that the plane-tree results transfer under standard conditioning.

minor comments (3)
  1. [Introduction] The introduction would benefit from a short table or paragraph explicitly mapping the four methods to the growth regimes (e.g., which method yields Poisson vs. normal limits and under which moment conditions on the degree sequence).
  2. [Section 2] Notation for the degree sequence (n_k) and the fringe-tree counts (X_n, Y_n, Z_n) is introduced gradually; a consolidated notation section or early display would improve readability.
  3. [Section 4] The statement of the auxiliary local-limit theorem (presumably Theorem X) should include a brief remark on whether the error term is uniform in the target value or only pointwise.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our manuscript, including recognition of the methodological comparison across regimes, the explicit error bounds, the auxiliary local-limit theorem, and the transfer to conditioned Galton-Watson trees. The recommendation for minor revision is noted; we will prepare a revised version incorporating any editorial or minor clarifications.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives Poisson and normal limits for growing fringe-tree counts in degree-constrained plane trees by applying four external standard tools (moments plus Gao-Wormald, Stein coupling, Cai-Devroye, exchangeable pairs) under explicitly stated growth regimes; the auxiliary local-limit theorem for sampling-without-replacement sums is proved independently and invoked only after its own derivation; the Galton-Watson extension is obtained simply by checking that the degree sequence satisfies the same hypotheses. No equation reduces to a prior result by definition, no fitted parameter is relabeled as a prediction, and no load-bearing step collapses to a self-citation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities can be extracted.

pith-pipeline@v0.9.0 · 5488 in / 1012 out tokens · 23150 ms · 2026-05-10T18:56:27.906734+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Random trees have heightOp ?nq.Ann

    Louigi Addario-Berry & Serte Donderwinkel. Random trees have heightOp ?nq.Ann. Prob- ability52 (2024), 2238–2280. MR 4815972

    work page 2024

  2. [2]

    A. D. Barbour, Lars Holst & Svante Janson.Poisson Approximation. Oxford University Press, Oxford, 1992. MR 1163825

    work page 1992

  3. [3]

    Undergraduate thesis, Royal Institute of Technology (KTH), Stockholm, c

    Michael Benedicks. Undergraduate thesis, Royal Institute of Technology (KTH), Stockholm, c. 1973.1

    work page 1973

  4. [4]

    An estimate of the modulus of the characteristic function of a lattice distribution with application to remainder term estimates in local limit theorems.Ann

    Michael Benedicks. An estimate of the modulus of the characteristic function of a lattice distribution with application to remainder term estimates in local limit theorems.Ann. Probability3(1975), 162–165. MR 0380927

    work page 1975

  5. [5]

    Fringe trees for random trees with given vertex degrees.Random Structures Algorithms66(2025), no

    Gabriel Berzunza Ojeda, Cecilia Holmgren & Svante Janson. Fringe trees for random trees with given vertex degrees.Random Structures Algorithms66(2025), no. 4, Paper e70001, 28 pp. MR 4931932

    work page 2025

  6. [6]

    Asymptotics of trees with a prescribed degree se- quence and applications.Random Structures & Algorithms44 (2014), 290–316

    Nicolas Broutin & Jean-Fran¸ cois Marckert. Asymptotics of trees with a prescribed degree se- quence and applications.Random Structures & Algorithms44 (2014), 290–316. MR 3188597

    work page 2014

  7. [7]

    A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees

    Xing Shi Cai & Luc Devroye. A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees. Preprint, 2016.arXiv:1602.03850v1 (Preliminary version of [8].)

    work page arXiv 2016

  8. [8]

    A study of large fringe and non-fringe subtrees in condi- tional Galton-Watson trees.ALEA Lat

    Xing Shi Cai & Luc Devroye. A study of large fringe and non-fringe subtrees in condi- tional Galton-Watson trees.ALEA Lat. Am. J. Probab. Math. Stat.14 (2017), 579–611. MR 3667924

    work page 2017

  9. [9]

    Exchangeable pairs and Poisson approximation.Probab

    Sourav Chatterjee, Persi Diaconis, and Elizabeth Meckes. Exchangeable pairs and Poisson approximation.Probab. Surv.2(2005), 64–106. MR 2121796

    work page 2005

  10. [10]

    Louis H. Y. Chen, Larry Goldstein & Qi-Man Shao.Normal Approximation by Stein’s Method. Springer-Verlag, Berlin, 2011. MR 2732624

    work page 2011

  11. [11]

    Springer-Verlag, Vienna, 2009

    Michael Drmota.Random Trees. Springer-Verlag, Vienna, 2009. MR 2484382

    work page 2009

  12. [12]

    On the central limit theorem for samples from a finite popula- tion.Magyar Tud

    Paul Erd˝ os & Alfr´ ed R´ enyi. On the central limit theorem for samples from a finite popula- tion.Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl.4(1959), 49–61. MR 0107294

    work page 1959

  13. [13]

    William Feller.An Introduction to Probability Theory and its Applications. Vol. II. 2nd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 0270403

    work page 1971

  14. [14]

    Zhicheng Gao & Nicholas C. Wormald. Asymptotic normality determined by high moments, and submap counts of random maps.Probab. Theory Related Fields.130 (2004), 368–376 MR 2095934

    work page 2004

  15. [15]

    B. V. Gnedenko & A. N. Kolmogorov.Limit Distributions for Sums of Independent Random Variables, Addison-Wesley Publishing Co., Inc., Cambridge, Mass, 1954. MR 0062975

    work page 1954

  16. [16]

    Allan Gut.Probability: A Graduate Course, 2nd ed., Springer, New York, 2013

    work page 2013

  17. [17]

    Limiting distributions in simple random sampling from a finite population

    Jaroslav H´ ajek. Limiting distributions in simple random sampling from a finite population. Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl.5(1960), 361–374. MR 0125612

    work page 1960

  18. [18]

    Asymptotic theory of rejective sampling with varying probabilities from a finite population.Ann

    Jaroslav H´ ajek. Asymptotic theory of rejective sampling with varying probabilities from a finite population.Ann. Math. Statist.35(1964), 1491–1523. MR 0178555 1We have unfortunately only heard about this paper on a local limit theorem for drawing without replacement, but we have not been able to find a copy. 34 GABRIEL BERZUNZA OJEDA, CECILIA HOLMGREN, ...

    work page 1964

  19. [19]

    Sampling from a finite population

    Thomas H¨ oglund. Sampling from a finite population. A remainder term estimate.Studia Sci. Math. Hungar.11(1976), no. 1-2, 69–74 (1978). MR 0545097

    work page 1976

  20. [20]

    Sampling from a finite population: a remainder term estimate.Scand

    Thomas H¨ oglund. Sampling from a finite population: a remainder term estimate.Scand. J. Statist.5(1978), no. 1, 69–71. MR 0471130

    work page 1978

  21. [21]

    Two conditional limit theorems with applications.Ann

    Lars Holst. Two conditional limit theorems with applications.Ann. Statist.7(1979), no. 3, 551–557. MR 0527490

    work page 1979

  22. [22]

    Simply generated trees, conditioned Galton–Watson trees, random alloca- tions and condensation.Probability Surveys9(2012), 103–252

    Svante Janson. Simply generated trees, conditioned Galton–Watson trees, random alloca- tions and condensation.Probability Surveys9(2012), 103–252. MR 2908619

    work page 2012

  23. [23]

    Asymptotic normality of fringe subtrees and additive functionals in con- ditioned Galton–Watson trees.Random Structures Algorithms48(2016), no

    Svante Janson. Asymptotic normality of fringe subtrees and additive functionals in con- ditioned Galton–Watson trees.Random Structures Algorithms48(2016), no. 1, 57–101. MR 3432572

    work page 2016

  24. [24]

    Wiley, New York, 2000

    Svante Janson, Tomasz Luczak & Andrzej Ruci´ nski.Random Graphs. Wiley, New York, 2000

    work page 2000

  25. [25]

    Limit theorems for samples from a finite population.J

    Miloslav Jiˇ rina. Limit theorems for samples from a finite population.J. Austral. Math. Soc. Ser. A32(1982), no. 3, 318–327. MR 0652408

    work page 1982

  26. [26]

    Olav Kallenberg.Foundations of Modern Probability, 2nd ed., Springer-Verlag, New York,

    work page

  27. [27]

    Petrov.Sums of Independent Random Variables

    Valentin V. Petrov.Sums of Independent Random Variables. Springer-Verlag, New York- Heidelberg, 1975. MR 0388499

    work page 1975

  28. [28]

    Ecole d’Et´ e de Probabilit´ es de Saint- Flour XXXII – 2002

    Jim Pitman.Combinatorial Stochastic Processes. Ecole d’Et´ e de Probabilit´ es de Saint- Flour XXXII – 2002. Lecture Notes in Mathematics, 1875. Springer-Verlag, Berlin, 2006. MR 2245368

    work page 2002

  29. [29]

    Limit theorems for sampling from finite populations.Ark

    Bengt Ros´ en. Limit theorems for sampling from finite populations.Ark. Mat.5(1965), 383–424. MR 0177437

    work page 1965

  30. [30]

    Fundamentals of Stein’s method.Probab

    Nathan Ross. Fundamentals of Stein’s method.Probab. Surv.8(2011), 210–293. MR 2861132

    work page 2011

  31. [31]

    V. M. Zolotarev.One-dimensional Stable Distributions.American Mathematical Society, Providence, RI, 1986. MR 0854867 Department of Mathematical Sciences, University of Liverpool, United Kingdom Email address:gabriel.berzunza-ojeda@liverpool.ac.uk URL:https://www.liverpool.ac.uk/mathematical-sciences/staff/gabriel-berzunza-ojeda/ Department of Mathematics,...

    work page 1986