arxiv: 2605.08706 · v2 · submitted 2026-05-09 · 🧮 math.PR · math.CO

Recognition: no theorem link

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

Ryo Imai

Pith reviewed 2026-05-12 01:02 UTC · model grok-4.3

classification 🧮 math.PR math.CO

keywords normal approximationconfiguration modeluniform simple graphStein's methodisolated edgesisolated 2-starsdegree sequencecoupling

0 comments

The pith

The numbers of isolated edges and isolated 2-stars in uniform simple graphs with given degrees are approximately normal with explicit finite-sample error bounds.

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

The paper derives the first quantitative normal approximation results for the counts of isolated edges and isolated 2-stars in the uniform simple random graph with a fixed degree sequence. It begins by establishing joint normal-Poisson approximation bounds in the configuration model for these counts together with the numbers of self-loops and double edges. Conditioning on the event that the configuration model produces a simple graph then transfers the approximation to the uniform model. A sympathetic reader would care because the uniform model is the natural one for many applications in network analysis, yet previous work lacked explicit error rates for these local subgraph counts.

Core claim

Under conditions on the degree sequence that keep the configuration model likely to be simple, the joint distribution of the number of isolated edges and the number of isolated 2-stars in the uniform simple graph is close in distribution to a bivariate normal, with explicit bounds on the total variation or Kolmogorov distance that are obtained by first approximating the corresponding counts in the configuration model via a new Stein's method for joint normal-Poisson approximation and then applying a new coupling of sums of indicators to pass to the conditioned simple graph.

What carries the argument

A new Stein's method for joint normal-Poisson approximation together with a coupling construction for sums of indicator variables, applied first in the configuration model and then transferred by conditioning on the absence of self-loops and multiple edges.

If this is right

The same bounds immediately supply normal approximations for the number of isolated edges or isolated 2-stars taken separately.
The error terms can be evaluated numerically for any given degree sequence to decide when the normal approximation is reliable.
The joint approximation controls the covariance between the two counts, which is useful for constructing confidence regions or test statistics.
The conditioning argument shows that any statistic whose distribution is already well approximated in the configuration model will inherit a comparable approximation in the uniform simple graph.

Where Pith is reading between the lines

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

The Stein-plus-coupling technique may extend directly to counts of larger isolated subgraphs or to other local statistics such as the number of isolated triangles.
For regular or nearly regular degree sequences the bounds should simplify and could be compared with known results for the Erdős–Rényi model.
The explicit dependence on the degree sequence makes it possible to test the approximation on real-world networks by plugging in their empirical degree sequences.

Load-bearing premise

The degree sequence must be such that the configuration model has positive probability of producing a simple graph and that the resulting error terms remain small enough to be useful.

What would settle it

For a concrete degree sequence satisfying the paper's implicit conditions, compute or simulate the exact Kolmogorov distance between the joint distribution of isolated edges and isolated 2-stars and the fitted bivariate normal and check whether it exceeds the paper's explicit 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 approximations for isolated edges and isolated 2-stars in the uniform simple graph with given degrees by extending Stein's method to joint normal-Poisson approximation in the configuration model then conditioning on simplicity.

read the letter

This paper provides the first finite-sample normal approximations for the numbers of isolated edges and isolated 2-stars in the uniform simple graph with given vertex degrees. It gets there by building a new Stein's method for joint normal-Poisson approximation to the configuration model counts, including self-loops and double edges, and then conditioning on simplicity. The new method and the coupling for indicator sums are the fresh parts, and they look like they could be reused. The paper does well in delivering explicit error bounds that are quantitative rather than asymptotic only. The potential soft spot is the one raised in the stress-test. The conditional normal approximation is only useful when the configuration model has a decent chance of being simple. The abstract leaves the degree conditions implicit, so the bounds might not stay small in all cases where the uniform model is defined. The full text probably specifies the regime, but if it doesn't tie the error explicitly to a lower bound on P(simple), that would be a minor gap. The rest of the argument seems to hold without circularity or other issues. This is for people in probabilistic combinatorics focused on random graphs with fixed degrees and approximation methods. It would be useful to someone extending Stein's method to graph models. It deserves a serious referee to check the details of the new method and the literature claim. I recommend sending it for peer review.

Referee Report

1 major / 1 minor

Summary. The paper considers the configuration model and the uniform simple graph with given degree sequence d. It derives quantitative error bounds for joint normal-Poisson approximations to the numbers of isolated edges, isolated 2-stars, self-loops and double edges in the configuration model. It further obtains normal approximation bounds for the numbers of isolated edges and isolated 2-stars conditioned on the configuration model being simple, claiming these are the first finite-sample results of this type for the uniform simple graph. The approach relies on a new Stein's method for joint normal-Poisson approximation and a new coupling for sums of indicators.

Significance. If the quantitative bounds hold under explicitly stated conditions on d that keep P(configuration model is simple) bounded away from zero, the results would provide the first explicit finite-n normal approximations for these subgraph counts in the uniform simple graph model. The methodological contributions—a new Stein's method extension and coupling technique—are strengths that could apply more broadly to dependent indicators in combinatorial settings.

major comments (1)

The main theorems on the conditional normal approximations (likely in the results section following the abstract) do not explicitly state or incorporate conditions on d (such as max d_i = o(n^{1/2}) or sum d_i(d_i-1) = O(n)) that ensure P(the configuration model is simple) is bounded below by a positive constant independent of n. Without this, the total-variation error bounds for the conditional law may be non-informative precisely in the regime where the uniform simple graph is well-defined, undermining the central claim of useful finite-sample approximations.

minor comments (1)

The abstract states that 'quantitative bounds are derived' but provides no explicit forms, theorem references, or degree conditions, which reduces immediate readability for assessing the scope of the results.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the constructive major comment. We address it directly below.

read point-by-point responses

Referee: The main theorems on the conditional normal approximations (likely in the results section following the abstract) do not explicitly state or incorporate conditions on d (such as max d_i = o(n^{1/2}) or sum d_i(d_i-1) = O(n)) that ensure P(the configuration model is simple) is bounded below by a positive constant independent of n. Without this, the total-variation error bounds for the conditional law may be non-informative precisely in the regime where the uniform simple graph is well-defined, undermining the central claim of useful finite-sample approximations.

Authors: We agree that the current theorem statements give general bounds that hold for arbitrary graphical degree sequences d, with the conditional error controlled by the unconditional error divided by P(the configuration model is simple). When this probability is not bounded away from zero, the resulting bound can indeed become uninformative. To address this and to make the finite-sample claims for the uniform simple graph fully rigorous and useful, we will revise the manuscript by explicitly adding standard conditions on d (e.g., max_i d_i = o(n^{1/2}) and sum_i d_i(d_i-1) = O(n)) to the statements of the main conditional approximation theorems. Under these conditions, P(the configuration model is simple) is bounded below by a positive constant depending only on the implicit constants in the O-notation. We will also add a short discussion in the introduction clarifying the regime in which the results apply. This change directly strengthens the central claim without altering the proofs. revision: yes

Circularity Check

0 steps flagged

No circularity; novel Stein's method and coupling yield independent bounds

full rationale

The paper derives quantitative error bounds for joint normal-Poisson approximation in the configuration model and normal approximation for isolated edges and 2-stars in the uniform simple graph by conditioning on simplicity. These bounds are obtained via a newly developed Stein's method for joint normal-Poisson approximation together with a new coupling approach to sums of indicators. No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the conditioning argument is a standard probabilistic device that does not force the target result from the inputs. The derivation chain is self-contained with independent mathematical content.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review yields minimal ledger entries; the work relies on standard configuration-model properties and Stein's method background without introducing new free parameters or entities.

axioms (1)

domain assumption Degree sequence d allows the configuration model to have positive probability of producing a simple graph
Required for the conditioning step to be meaningful and for the normal approximation to apply to the uniform simple graph.

pith-pipeline@v0.9.0 · 5423 in / 1152 out tokens · 45360 ms · 2026-05-12T01:02:22.081760+00:00 · methodology