The Distribution Of Subtrees In Dense Graphs And The Roots Of The Subtree Polynomial

Ruoyu Wang; Stephan Wagner

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

The Distribution Of Subtrees In Dense Graphs And The Roots Of The Subtree Polynomial

Stephan Wagner , Ruoyu Wang This is my paper

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

classification 🧮 math.CO

keywords subtree polynomialdense graphsPoisson distributiongraph subtreesroots of polynomialsasymptotic distributionminimum degreeenumeration

0 comments

The pith

In dense connected graphs, the number of vertices missing from a random subtree is asymptotically Poisson-distributed, forcing all roots of the subtree polynomial close to zero.

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

The paper considers connected graphs on n vertices whose minimum degree is at least a fixed positive fraction of n. It proves that a uniformly random subtree leaves out a number of vertices whose distribution converges to a Poisson law as n grows. This distributional fact is then used to conclude that every complex root of the subtree polynomial must lie inside a disk of radius tending to zero. A reader might care because the result ties the typical size of subtrees directly to the analytic location of the roots of their generating function.

Core claim

For a connected graph G on n vertices with minimum degree at least cn for fixed c>0, if a subtree is chosen uniformly at random, then the number of vertices of G not contained in the subtree converges in distribution to a Poisson random variable. As a direct consequence, every root of the subtree polynomial S(G;x) = sum s_k(G) x^k satisfies |root| = o(1) as n tends to infinity.

What carries the argument

The asymptotic Poisson distribution of the number of excluded vertices in a uniformly random subtree, which determines the radius containing all roots of the subtree polynomial.

If this is right

The probability that a random subtree contains exactly k vertices is asymptotically given by the Poisson probability for the complement count n-k.
The subtree polynomial is asymptotically dominated by its highest-degree terms when the variable is bounded away from the origin.
All roots of the subtree polynomial must approach the origin, so the polynomial cannot vanish at any fixed positive distance from zero for large n.
The expected number of subtrees of each size is governed by the Poisson probabilities shifted to the top degree.

Where Pith is reading between the lines

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

The same Poisson mechanism may locate roots for other subgraph-counting polynomials on dense graphs.
The result suggests that random dense graphs, such as those with edge probability bounded away from zero, should exhibit analogous root behavior.
One could test the Poisson limit numerically on explicit dense graphs like complete graphs minus a matching or on random regular graphs of high degree.

Load-bearing premise

The graphs are connected and have minimum degree linear in the number of vertices.

What would settle it

A sequence of dense connected graphs in which the number of missing vertices in a random subtree fails to converge in distribution to Poisson, or in which the subtree polynomial has at least one root whose modulus stays bounded away from zero.

read the original abstract

For a graph $G$ with $n$ vertices and a positive integer $k \leq n$, let $s_k(G)$ be the number of subtrees (subgraphs that are trees, not necessarily induced) of $G$ with $k$ vertices. The subtree polynomial of $G$ is $S(G;x) = \sum_{k=1}^n s_k(G) x^k$. In this paper, we consider dense connected graphs with a minimum degree that is linear in the number of vertices. We prove that the number of missing vertices in a random subtree is asymptotically Poisson-distributed and deduce that all the roots of the subtree polynomial have to be close to $0$.

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

The Poisson limit on missing vertices in random subtrees of dense graphs is the new piece, and the root bound for the subtree polynomial follows only if the proof adds quantitative control beyond plain distributional convergence.

read the letter

The main thing to know is that this paper proves the number of missing vertices in a random subtree of a dense connected graph is asymptotically Poisson distributed, and from that deduces that the roots of the subtree polynomial all lie close to zero. The Poisson limit is the genuinely new part. It gives a precise asymptotic for subtree sizes under the minimum degree condition, which organizes the counts s_k in a useful way. The authors set up the polynomial S(G;x) clearly and connect the distribution to the coefficients in a direct manner. What they do well is the application to root locations. If the proof supplies the necessary control on the probability generating function, this yields a clean statement that all roots approach the origin. The potential soft spot is exactly the one in the stress-test note. Distributional convergence alone does not guarantee the absence of roots at moderate distances without some uniformity or tail bounds. The paper must include quantitative estimates or an application of a theorem like Hurwitz that accounts for the approximation error on larger disks. Assuming the full text has that, the argument holds; if it relies only on pointwise limits, the root claim would be weaker than stated. The assumptions of connectedness and linear minimum degree are necessary for the Poisson to kick in and are stated upfront. This is for people in combinatorial graph theory who work with generating functions and asymptotic distributions. A reader focused on subtree enumeration or polynomial roots in graphs would get concrete value from the distribution theorem. It deserves a serious referee. The claims are specific and the technical core can be reviewed for correctness. I recommend sending the paper to peer review.

Referee Report

2 major / 2 minor

Summary. The paper considers connected graphs G on n vertices with minimum degree Ω(n). It proves that if T is a uniform random subtree of G, then the number of missing vertices M_n = n - |V(T)| converges in distribution to a Poisson random variable (with parameter depending on the density). From this it deduces that every root r of the subtree polynomial S(G;x) = ∑ s_k(G) x^k satisfies |r| → 0 as n → ∞.

Significance. If the claims hold, the Poisson limit supplies a precise asymptotic description of subtree sizes in dense graphs, while the root conclusion gives a uniform location result for the zeros of the subtree generating function. Both are potentially useful for enumeration problems and for analytic combinatorics on graphs. The argument is presented as a direct asymptotic analysis without parameter fitting or circularity.

major comments (2)

[§4] §4 (deduction of root bound): distributional convergence of M_n to Poisson(λ) implies pointwise convergence of the normalized probability generating function p_n(z) = E[z^{M_n}] at each fixed z. However, to conclude that all zeros of the reversed polynomial p(z) lie outside every fixed disk |z| < R (hence all roots of S(G;x) satisfy |x| < 1/R), uniform control on |z| ≤ R_n with R_n → ∞ or an application of Rouché/Hurwitz that bounds the tail contribution is required. The manuscript appears to invoke only pointwise convergence; this is insufficient to rule out zeros of p at moderate |z| arising from large-j tails.
[Theorem 1.1 / §3] Theorem 1.1 and the proof of the Poisson limit (§3): the reduction from the minimum-degree assumption to the explicit Poisson parameter λ relies on a specific counting argument for the probability that a given vertex is excluded. The manuscript does not appear to supply a uniform error bound on the total-variation distance to Poisson that is strong enough to support the subsequent analytic continuation needed for the root claim.

minor comments (2)

[§2] Notation: the symbol λ is used both for the Poisson parameter and (implicitly) for a density constant; a single clarifying sentence would avoid confusion.
[Theorem 1.1] The statement of the main theorem should explicitly record the dependence of λ on the minimum-degree constant c.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying these points requiring clarification. The main results on the Poisson limit for missing vertices and the consequent root bounds for the subtree polynomial hold under the stated density assumptions, but we agree that the manuscript's presentation of the analytic step from distributional convergence to root locations needs strengthening with explicit uniform estimates. We will revise accordingly.

read point-by-point responses

Referee: [§4] §4 (deduction of root bound): distributional convergence of M_n to Poisson(λ) implies pointwise convergence of the normalized probability generating function p_n(z) = E[z^{M_n}] at each fixed z. However, to conclude that all zeros of the reversed polynomial p(z) lie outside every fixed disk |z| < R (hence all roots of S(G;x) satisfy |x| < 1/R), uniform control on |z| ≤ R_n with R_n → ∞ or an application of Rouché/Hurwitz that bounds the tail contribution is required. The manuscript appears to invoke only pointwise convergence; this is insufficient to rule out zeros of p at moderate |z| arising from large-j tails.

Authors: We agree that pointwise convergence of the pgf is not by itself sufficient to control the zeros uniformly. The original argument in §4 used the Poisson limit to conclude that roots of S(G;x) approach zero, but did not spell out the passage from pointwise to uniform control on compact sets. In the revision we will insert a short lemma applying Hurwitz's theorem: we first obtain tail bounds P(M_n > K) ≤ C e^{-cK} uniformly in n from the explicit moment calculations in §3, then show that p_n(z) converges uniformly to the Poisson pgf on any fixed disk |z| ≤ R. This rules out zeros inside |z| < R for large n and yields the claimed root bound without altering the statement of the theorem. revision: yes
Referee: [Theorem 1.1 / §3] Theorem 1.1 and the proof of the Poisson limit (§3): the reduction from the minimum-degree assumption to the explicit Poisson parameter λ relies on a specific counting argument for the probability that a given vertex is excluded. The manuscript does not appear to supply a uniform error bound on the total-variation distance to Poisson that is strong enough to support the subsequent analytic continuation needed for the root claim.

Authors: The counting argument in §3 already produces an explicit expression for the probability that any fixed vertex is excluded and shows that the joint exclusion probabilities factor asymptotically under the Ω(n) minimum-degree hypothesis. We concede that an explicit uniform total-variation bound d_TV(Law(M_n), Poisson(λ)) = O(1/n) is not written down. In the revision we will add a lemma deriving this bound directly from the same inclusion-exclusion estimates used for the factorial moments; the resulting O(1/n) rate immediately implies uniform convergence of the pgfs on compact disks and thereby justifies the analytic step in the revised §4. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation is self-contained asymptotic analysis

full rationale

The paper proves asymptotic Poisson convergence for the number of missing vertices in a uniform random subtree of dense connected graphs (min-degree Ω(n)) via direct probabilistic arguments on subtree enumeration and generating functions. It then deduces root locations of S(G;x) from the resulting coefficient asymptotics. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the two parts are linked by standard analytic combinatorics but remain independent of the target claims. The derivation does not rename known results or smuggle ansatzes via prior self-work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definition of a connected graph with linear minimum degree and on the usual probabilistic method for sampling subtrees; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption The graph is connected and has minimum degree at least c n for some fixed c > 0.
Invoked in the abstract as the setting in which the Poisson limit holds.

pith-pipeline@v0.9.0 · 5410 in / 1105 out tokens · 22543 ms · 2026-05-07T15:38:56.956984+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

J. I. Brown and L. Mol. On the roots of the subtree polynomial.European J. Combin., 89:103181, 13, 2020

work page 2020
[2]

A. J. Chin, G. Gordon, K. J. MacPhee, and C. Vincent. Subtrees of graphs.J. Graph Theory, 89(4):413– 438, 2018

work page 2018
[3]

Hladký, A

J. Hladký, A. Nachmias, and T. Tran. The local limit of the uniform spanning tree on dense graphs.J. Stat. Phys., 173(3-4):502–545, 2018

work page 2018
[4]

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
[5]

R. E. Jamison. Monotonicity of the mean order of subtrees.J. Combin. Theory Ser. B, 37(1):70–78, 1984

work page 1984
[6]

R. E. Jamison. Alternating Whitney sums and matchings in trees. I.Discrete Math., 67(2):177–189, 1987

work page 1987
[7]

R. E. Jamison. Alternating Whitney sums and matchings in trees. II.Discrete Math., 79(2):177–189, 1990

work page 1990
[8]

Z. Luo, K. Xu, and J. Tian. Random subtrees and unimodal sequences in graphs.Discrete Math., 347(1):Paper No. 113654, 13, 2024

work page 2024
[9]

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
[10]

Pemantle and Y

R. Pemantle and Y. Peres. Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures.Combin. Probab. Comput., 23(1):140–160, 2014

work page 2014
[11]

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
[12]

S. Wagner. On the probability that a random subtree is spanning.J. Graph Theory, 98(2):195–215, 2021

work page 2021

[1] [1]

J. I. Brown and L. Mol. On the roots of the subtree polynomial.European J. Combin., 89:103181, 13, 2020

work page 2020

[2] [2]

A. J. Chin, G. Gordon, K. J. MacPhee, and C. Vincent. Subtrees of graphs.J. Graph Theory, 89(4):413– 438, 2018

work page 2018

[3] [3]

Hladký, A

J. Hladký, A. Nachmias, and T. Tran. The local limit of the uniform spanning tree on dense graphs.J. Stat. Phys., 173(3-4):502–545, 2018

work page 2018

[4] [4]

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

[5] [5]

R. E. Jamison. Monotonicity of the mean order of subtrees.J. Combin. Theory Ser. B, 37(1):70–78, 1984

work page 1984

[6] [6]

R. E. Jamison. Alternating Whitney sums and matchings in trees. I.Discrete Math., 67(2):177–189, 1987

work page 1987

[7] [7]

R. E. Jamison. Alternating Whitney sums and matchings in trees. II.Discrete Math., 79(2):177–189, 1990

work page 1990

[8] [8]

Z. Luo, K. Xu, and J. Tian. Random subtrees and unimodal sequences in graphs.Discrete Math., 347(1):Paper No. 113654, 13, 2024

work page 2024

[9] [9]

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

[10] [10]

Pemantle and Y

R. Pemantle and Y. Peres. Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measures.Combin. Probab. Comput., 23(1):140–160, 2014

work page 2014

[11] [11]

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

[12] [12]

S. Wagner. On the probability that a random subtree is spanning.J. Graph Theory, 98(2):195–215, 2021

work page 2021