Normal approximation of the numbers of isolated edges and isolated 2-stars in uniform simple graphs with given vertex degrees

Ryo Imai

arxiv: 2605.08706 · v4 · pith:TQS7TT2Hnew · submitted 2026-05-09 · 🧮 math.PR · math.CO

Normal approximation of the numbers of isolated edges and isolated 2-stars in uniform simple graphs with given vertex degrees

Ryo Imai This is my paper

Pith reviewed 2026-05-14 21:52 UTC · model grok-4.3

classification 🧮 math.PR math.CO MSC 60F0505C8060C05

keywords normal approximationStein's methodconfiguration modelsimple graphsisolated edgesisolated 2-starsdegree sequencesrandom graphs

0 comments

The pith

New Stein couplings deliver the first finite-sample normal approximation bounds for isolated edges and isolated 2-stars in uniform simple graphs with prescribed degrees.

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

The paper derives explicit error bounds that quantify how closely the counts of isolated edges and isolated 2-stars follow normal distributions in the uniform model of simple graphs with a fixed degree sequence. It first obtains joint normal-Poisson error bounds for these counts together with self-loops and double edges inside the configuration model, then transfers the normal bounds to the simple-graph model by conditioning on the event that the configuration model produces no loops or multiples. A reader would care because these bounds let one make precise finite-n statements about local subgraph statistics in networks whose degrees are known in advance, without passing to an asymptotic regime. The work rests on a newly developed Stein method that handles joint normal and Poisson approximation together with a fresh coupling construction for sums of indicators.

Core claim

We derive quantitative bounds for the errors in (i) joint normal-Poisson approximation to the numbers of isolated edges, isolated 2-stars, self-loops and double edges in the configuration model, and (ii) normal approximation to the numbers of isolated edges and isolated 2-stars conditioned on that the configuration model is simple. The latter provides the first finite sample normal approximation results for the uniform simple graph with given vertex degrees.

What carries the argument

A new Stein's method for joint normal-Poisson approximation together with a new coupling construction for sums of indicators, applied first in the configuration model and then conditioned on simplicity.

If this is right

The normal approximation error for isolated edges and isolated 2-stars is bounded by an explicit function of the degree sequence and n that vanishes under standard regularity conditions.
Conditioning on the configuration model being simple transfers the normal limit directly to the uniform simple-graph model.
The same Stein-coupling technique simultaneously controls self-loops and double edges, which are the main obstructions to simplicity.
The bounds hold for finite n and do not require the degree sequence to become dense or sparse in any particular way beyond the regularity conditions.

Where Pith is reading between the lines

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

The same coupling framework could be applied to other small-subgraph counts such as isolated triangles once the appropriate Stein equations are solved.
The explicit error rates open the possibility of using observed counts of isolated edges to test whether a real network is consistent with a given degree sequence under the uniform simple model.
Because the bounds are non-asymptotic, they could be used to calibrate simulation studies that generate graphs from a prescribed degree sequence.

Load-bearing premise

The given degree sequence must satisfy regularity conditions that make the configuration model simple with high probability so that the Stein couplings produce the stated quantitative error bounds.

What would settle it

Compute the exact distribution of the number of isolated edges for a small explicit degree sequence (for example n=20 with all degrees equal to 3) and check whether the Wasserstein or total-variation distance to the matching normal law exceeds the paper's claimed bound.

read the original abstract

We consider the configuration model and the uniform simple graph with given degree sequence $\boldsymbol{d}=\left(d_i\right)_{i=1}^n$. We derive quantitative bounds for the errors in (i) joint normal-Poisson approximation to the numbers of isolated edges, isolated 2-stars, self-loops and double edges in the configuration model, and (ii) normal approximation to the numbers of isolated edges and isolated 2-stars conditioned on that the configuration model is simple. The latter provides the first finite sample normal approximation results for the uniform simple graph with given vertex degrees. To achieve this, we develop a new Stein's method for joint normal-Poisson approximation and a new coupling approach to sums of indicators, which may be of independent interest.

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

This paper gives the first finite-sample normal approximation bounds for isolated edges and isolated 2-stars in uniform simple graphs with given degrees by building new Stein and coupling tools for the configuration model and then conditioning on simplicity.

read the letter

The main point is that this work provides the first quantitative, finite-sample normal approximation results for the counts of isolated edges and isolated 2-stars in the uniform model of simple graphs with a prescribed degree sequence. The authors accomplish this by first establishing joint normal-Poisson approximations in the configuration model using freshly developed Stein's method and coupling techniques, and then transferring the bounds to the conditioned simple graph. The development of the new Stein's method for joint normal-Poisson approximation stands out as a technical advance that could apply more broadly. Similarly, the new coupling approach to sums of indicators offers a way to handle dependencies in indicator variables that might be useful in other combinatorial probability settings. The paper does a good job of making the error bounds explicit, moving beyond the usual asymptotic statements in this literature. The conditioning argument is handled carefully by incorporating the probability that the configuration model produces a simple graph. A potential soft spot is in how the error bound for the conditional distribution behaves. Since the approximation error includes a term controlled by the reciprocal of the probability that the configuration model is simple, the final bound's usefulness depends on how small that probability can be under the paper's degree sequence assumptions. The abstract refers to regularity conditions that presumably make this probability bounded away from zero, but it would be worth verifying whether the bound remains o(1) in the interesting regime where the variance of the subgraph count is not too small. If the conditions only ensure a slowly vanishing probability, the normal approximation might not be as sharp as claimed for all cases. Overall, this paper targets researchers in probabilistic combinatorics, particularly those focused on random graphs with degree constraints and approximation methods like Stein's. A reader looking for explicit error bounds on subgraph counts in simple graphs will find it relevant. The work demonstrates solid technical engagement and introduces tools that merit further exploration. I would recommend sending this to peer review. The novelty in the methods and the claimed first finite-sample result make it worth a detailed referee report, even if some aspects of the conditioning step need extra scrutiny.

Referee Report

2 major / 1 minor

Summary. The paper derives quantitative error bounds for (i) joint normal-Poisson approximation to the counts of isolated edges, isolated 2-stars, self-loops and double edges in the configuration model with given degree sequence d, and (ii) normal approximation to the counts of isolated edges and isolated 2-stars in the uniform simple graph conditioned on the configuration model being simple. The latter is obtained by applying new Stein couplings and a new coupling argument for sums of indicators to the configuration model and then conditioning on simplicity; the abstract states that this yields the first finite-sample normal approximation results for these quantities in uniform simple graphs with prescribed degrees.

Significance. If the stated quantitative bounds hold under the paper's regularity conditions on d, the work supplies the first explicit finite-sample normal approximation theorems for these subgraph counts in the uniform simple graph model. This is a substantive advance over purely asymptotic results in random graph theory and supplies a methodological contribution via the new Stein normal-Poisson couplings that may be reusable for other conditioned configuration-model statistics.

major comments (2)

[Abstract / main conditional theorem] Abstract and the statement of the main conditional theorem: the error bound for the normal approximation to the conditional distribution contains a term of order 1/P(configuration model is simple). The paper invokes regularity conditions (presumably max d_i = o(n^{1/3}) or sum d_i(d_i-1) = O(n)) under which this probability is bounded below by a positive constant, but does not explicitly track the dependence of the final error on this probability or verify that the bound remains o(1) uniformly in the regime where the variance of the isolated-edge or isolated-2-star count is positive and growing.
[Main results section] The precise degree-sequence hypotheses under which the configuration model is simple with probability bounded away from zero are not stated in the theorems themselves; without an explicit lower bound on P(simple) that is uniform in the variance-positive regime, it is impossible to confirm that the claimed quantitative normal approximation is non-vacuous.

minor comments (1)

[Abstract] The abstract refers to 'new techniques' without a one-sentence outline of the key Stein coupling construction; adding such a sentence would improve readability for readers outside the immediate Stein-method community.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We appreciate the recognition of the novelty of the Stein couplings and the potential impact of the finite-sample bounds. We address each major comment below and will revise the manuscript to incorporate the suggested clarifications.

read point-by-point responses

Referee: [Abstract / main conditional theorem] Abstract and the statement of the main conditional theorem: the error bound for the normal approximation to the conditional distribution contains a term of order 1/P(configuration model is simple). The paper invokes regularity conditions (presumably max d_i = o(n^{1/3}) or sum d_i(d_i-1) = O(n)) under which this probability is bounded below by a positive constant, but does not explicitly track the dependence of the final error on this probability or verify that the bound remains o(1) uniformly in the regime where the variance of the isolated-edge or isolated-2-star count is positive and growing.

Authors: We agree that the dependence on 1/P(simple) merits explicit tracking for full transparency. In the revised version we will restate the conditional error bound with the factor 1/P(simple) kept visible, and we will add a short verification (in the proof of the main theorem) showing that under the regularity conditions max d_i = o(n^{1/3}) and sum d_i(d_i-1) = O(n) one has P(simple) >= c > 0 with c independent of n. Consequently the overall bound remains o(1) whenever the variance of the isolated-edge or isolated-2-star count is positive and tends to infinity. These additions will appear both in the abstract and in the statement of the main conditional theorem. revision: yes
Referee: [Main results section] The precise degree-sequence hypotheses under which the configuration model is simple with probability bounded away from zero are not stated in the theorems themselves; without an explicit lower bound on P(simple) that is uniform in the variance-positive regime, it is impossible to confirm that the claimed quantitative normal approximation is non-vacuous.

Authors: We accept the criticism that the hypotheses should be stated inside the theorem statements themselves. In the revision we will insert the precise conditions (max d_i = o(n^{1/3}) and sum d_i(d_i-1) = O(n)) directly into the hypotheses of the main conditional theorem, together with the resulting uniform lower bound P(simple) >= c > 0. This makes the non-vacuous character of the quantitative bound immediate in the variance-positive regime. revision: yes

Circularity Check

0 steps flagged

No circularity: new Stein couplings and conditioning arguments are independent of the target result

full rationale

The paper introduces a new Stein's method for joint normal-Poisson approximation and a new coupling approach for sums of indicators, then applies them first to the configuration model and subsequently conditions on the simplicity event. These steps rely on original analytic bounds and couplings rather than any self-definitional reduction, fitted input renamed as prediction, or load-bearing self-citation chain. The central finite-sample normal approximation for the uniform simple graph is obtained directly from the new tools under stated regularity conditions on the degree sequence; no equation or claim reduces to its own inputs by construction. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard background results from Stein's method and configuration-model theory together with regularity conditions on the degree sequence that are typical but not enumerated in the abstract.

axioms (1)

domain assumption Standard regularity conditions on the degree sequence hold so that the configuration model is simple with high probability and the Stein couplings produce the stated error bounds.
The quantitative bounds are derived under these conditions, which are invoked implicitly for the configuration-model and conditioning steps.

pith-pipeline@v0.9.0 · 5423 in / 1214 out tokens · 48272 ms · 2026-05-14T21:52:27.512388+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

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

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We develop a new Stein’s method for joint normal-Poisson approximation and a new coupling approach to sums of indicators... quantitative bounds for... normal approximation to the numbers of isolated edges and isolated 2-stars conditioned on that the configuration model is simple.
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat ≃ Nat recovery unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 3.1... bound (47) expressed in terms of the new coupling (46) and the smoothness estimates of the Stein solution fh

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.