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

Ryo Imai

REVIEW 2 major objections 2 minor 71 references

Quantitative normal approximation bounds are established for isolated edges and 2-stars in uniform simple graphs with given degrees.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-30 23:13 UTC pith:TQS7TT2H

load-bearing objection The paper gives the first finite-n normal bounds for isolated edges and 2-stars in the uniform simple graph via a new Stein method, but the conditioning step risks inflating errors if P(simple) is not controlled. the 2 major comments →

arxiv 2605.08706 v4 pith:TQS7TT2H 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

classification math.PR math.CO

keywords normal approximationStein's methodconfiguration modelisolated edges2-starssimple graphsdegree sequence

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper derives explicit error bounds for approximating the distributions of the numbers of isolated edges and isolated 2-stars by normals, first in the configuration model jointly with Poisson for loops and multiples, then conditioned on the graph being simple. The approach uses a new Stein's method for joint normal-Poisson approximation and a coupling for indicator sums. A reader would care if they need finite-sample guarantees rather than asymptotics for statistical properties of random graphs with fixed degrees. The results apply to the uniform distribution over simple graphs with the given degree sequence.

Core claim

The paper claims to provide the first finite sample normal approximation results for the numbers of isolated edges and isolated 2-stars in the uniform simple graph with given vertex degrees, achieved via new Stein bounds and couplings.

What carries the argument

New Stein's method for joint normal-Poisson approximation and a new coupling approach to sums of indicators.

Load-bearing premise

The degree sequence satisfies regularity conditions that ensure the configuration model is simple with positive probability and that additional error terms do not dominate the Stein bounds.

What would settle it

For a specific small degree sequence satisfying the conditions, simulate many configuration models, compute the empirical distribution of isolated edges, and verify whether the normal approximation error is smaller than the paper's bound.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

The error bounds are quantitative and finite-sample.
They transfer from configuration model to the uniform simple graph via conditioning.
The methods may interest researchers studying other subgraph statistics in random graphs.

Where Pith is reading between the lines

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

The coupling technique could be adapted to approximate other counts like triangles in similar models.
These bounds might allow construction of confidence intervals for observed network motifs without large-n assumptions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

The paper gives the first finite-n normal bounds for isolated edges and 2-stars in the uniform simple graph via a new Stein method, but the conditioning step risks inflating errors if P(simple) is not controlled.

read the letter

The one or two things to know: this paper claims the first finite-sample normal approximation bounds for the numbers of isolated edges and isolated 2-stars in the uniform simple graph with given degrees, and it develops a new Stein's method for joint normal-Poisson approximation together with a new coupling for sums of indicators.

It handles the configuration model part cleanly, producing explicit joint bounds there. The new tools look like they could be reused in other approximation settings.

The soft spot is the move to the conditioned model. The error bound after conditioning is at most the unconditioned error divided by P(the configuration is simple). For many degree sequences that satisfy only the usual conditions for few multiples, this probability can be exponentially small, which would make the final bound useless. The abstract does not list the exact regularity conditions, so it is unclear whether the paper keeps P(simple) bounded away from zero or shows the bounds stay useful anyway. If the proofs do not address this, the main claim for the uniform model is weaker than stated.

The presentation follows standard Stein machinery with no sign of circularity or fitted quantities. The citation pattern is normal for the area.

This paper is for specialists in probabilistic combinatorics who work on quantitative subgraph counts in degree-constrained graphs. A reader who needs explicit error terms or new Stein couplings would get concrete value from it.

It deserves a serious referee because it supplies the first such bounds and uses technically involved methods.

Recommendation: send it to peer review, but ask the referees to check how the conditioning error is controlled and whether the regularity conditions prevent blow-up.

Referee Report

2 major / 2 minor

Summary. The paper develops a new Stein's method for joint normal-Poisson approximation together with a coupling argument for sums of indicators. It first obtains explicit error bounds for the joint distribution of the numbers of isolated edges, isolated 2-stars, self-loops and double edges in the configuration model with given degree sequence d. These bounds are then transferred, via the new coupling, to yield normal approximation bounds for the same two subgraph counts in the uniform simple graph (i.e., the configuration model conditioned on being simple). The authors state that the conditioned results are the first finite-sample normal approximations available for these statistics under a prescribed degree sequence.

Significance. If the stated error bounds remain valid after conditioning and under the paper's regularity assumptions on d, the work supplies the first quantitative rates for normal approximation of local subgraph counts in the uniform model with fixed degrees. The new Stein and coupling techniques are presented as potentially reusable tools and could strengthen the statistical toolkit for networks with heterogeneous degrees.

major comments (2)

[Theorem 1.2 and the paragraph following the coupling construction] The transfer step from the configuration model to the conditioned simple graph (the central claim of the paper) multiplies the unconditioned distance by at most 1/P(simple). The regularity conditions stated for d (presumably in the assumptions preceding the main theorems) are the same minimal conditions that already appear in the literature for Poisson approximation of self-loops and double edges; under those conditions P(simple) can still be as small as exp(-Ω(∑ d_i²/n)). No explicit lower bound on P(simple) or compensating argument is supplied that would keep the final normal-approximation error o(1).
[Assumption 2.1 and the statement of the main normal-approximation theorem for the simple graph] The joint normal-Poisson bound in the unconditioned model is derived under the assumption that the maximum degree is o(n^{1/2}). This is precisely the regime in which the conditioning probability can decay exponentially, so the two parts of the argument are in tension; the manuscript does not reconcile them with a stronger assumption or a direct analysis of the conditioned indicators.

minor comments (2)

[§2] Notation for the isolated-edge and isolated-2-star counts is introduced only in the abstract and reappears without redefinition in the theorems; a short notational table or explicit definition in §2 would improve readability.
[Theorems 3.1 and 4.2] The abstract claims the results are 'parameter-free' in the sense of explicit constants, yet the error expressions contain several universal constants whose numerical values are not tracked; listing the dependence on these constants in the final display of each theorem would strengthen the claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the key technical tension in the transfer from the configuration model to the uniform simple graph. Both major comments concern the same issue: whether the normal-approximation bounds remain valid after conditioning when P(simple) may be small. We address each point below and will revise the manuscript by adding a standard strengthening of the degree assumptions that guarantees P(simple) is bounded away from zero.

read point-by-point responses

Referee: [Theorem 1.2 and the paragraph following the coupling construction] The transfer step from the configuration model to the conditioned simple graph (the central claim of the paper) multiplies the unconditioned distance by at most 1/P(simple). The regularity conditions stated for d (presumably in the assumptions preceding the main theorems) are the same minimal conditions that already appear in the literature for Poisson approximation of self-loops and double edges; under those conditions P(simple) can still be as small as exp(-Ω(∑ d_i²/n)). No explicit lower bound on P(simple) or compensating argument is supplied that would keep the final normal-approximation error o(1).

Authors: We agree that the current argument multiplies the total-variation distance by 1/P(simple) and that the stated assumptions on d permit P(simple) to decay exponentially. This is a substantive gap in the manuscript as written. To correct it we will add the explicit assumption that ∑_{i=1}^n d_i(d_i-1) = O(n). Under this condition standard estimates on the configuration model yield P(simple) ≥ c > 0 for some absolute constant c (depending only on the implicit constant in the O(n) bound). Consequently the error bounds for the uniform simple graph remain of the same order as the configuration-model bounds. We will update the statements of Theorems 1.1–1.2, the paragraph after the coupling construction, and the list of assumptions to include this condition. revision: yes
Referee: [Assumption 2.1 and the statement of the main normal-approximation theorem for the simple graph] The joint normal-Poisson bound in the unconditioned model is derived under the assumption that the maximum degree is o(n^{1/2}). This is precisely the regime in which the conditioning probability can decay exponentially, so the two parts of the argument are in tension; the manuscript does not reconcile them with a stronger assumption or a direct analysis of the conditioned indicators.

Authors: The o(n^{1/2}) bound on maximum degree is required for the Stein-equation estimates and moment calculations in the joint normal-Poisson approximation. We acknowledge that this regime is compatible with exponentially small P(simple). The additional assumption ∑ d_i(d_i-1) = O(n) that we will introduce (see response to the first comment) is compatible with maximum degree o(n^{1/2}) while ensuring that the expected number of loops and double edges remains bounded; this removes the tension without requiring a direct analysis of the conditioned indicators. The revised Assumption 2.1 will state both the original o(n^{1/2}) bound and the new O(n) condition on the sum of d_i(d_i-1). revision: yes

Circularity Check

0 steps flagged

No circularity: new Stein method and coupling presented as independent tools for the bounds

full rationale

The paper derives quantitative error bounds for joint normal-Poisson approximation in the configuration model and normal approximation in the conditioned simple graph by developing a new Stein's method for joint normal-Poisson approximation and a new coupling approach to sums of indicators. These are explicitly introduced as novel contributions that may be of independent interest, with no indication that the central results reduce by definition or construction to fitted parameters, prior self-citations, or renamed known patterns. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no explicit free parameters, axioms, or invented entities; all technical assumptions remain implicit.

pith-pipeline@v0.9.1-grok · 5654 in / 1000 out tokens · 19163 ms · 2026-06-30T23:13:27.977626+00:00 · methodology

0 comments

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.

Review history (3 revisions) →

discussion (0)

Reference graph

Works this paper leans on

71 extracted references · 2 canonical work pages · 2 internal anchors

[1]

W. J. Anderson.Continuous-time Markov chains. Springer Series in Statistics: Probability and its Applications. Springer-Verlag, New York, 1991. An applications-oriented approach

1991
[2]

Angel, R

O. Angel, R. van der Hofstad, and C. Holmgren. Limit laws for self-loops and multiple edges in the configuration model.Ann. Inst. Henri Poincar´ e Probab. Stat., 55(3):1509–1530, 2019. [Author name corrected by publisher]

2019
[3]

Arratia, L

R. Arratia, L. Goldstein, and L. Gordon. Two moments suffice for Poisson approximations: the Chen-Stein method.Ann. Probab., 17(1):9–25, 1989

1989
[4]

Central limit theorem for statistics of subcritical configuration models

S. Athreya and D. Yogeshwaran. Central limit theorem for statistics of subcritical configu- ration models.arXiv e-prints, page arXiv:1808.06778, Aug. 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018
[5]

Ball and P

F. Ball and P. Neal. The asymptotic variance of the giant component of configuration model random graphs.Ann. Appl. Probab., 27(2):1057–1092, 2017

2017
[6]

A. D. Barbour. Stein’s method and Poisson process convergence.J. Appl. Probab., 25(A):175–184, 1988. A celebration of applied probability

1988
[7]

A. D. Barbour. Multivariate Poisson-binomial approximation using Stein’s method. In Stein’s method and applications, volume 5 ofLect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., pages 131–142. Singapore Univ. Press, Singapore, 2005

2005
[8]

A. D. Barbour, L. Holst, and S. Janson.Poisson approximation, volume 2 ofOxford Studies in Probability. The Clarendon Press, Oxford University Press, New York, 1992. Oxford Science Publications

1992
[9]

A. D. Barbour and A. R¨ ollin. Central limit theorems in the configuration model.Ann. Appl. Probab., 29(2):1046–1069, 2019

2019
[10]

Bollob´ as

B. Bollob´ as. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.European J. Combin., 1(4):311–316, 1980

1980
[11]

Bollob´ as and O

B. Bollob´ as and O. Riordan. An old approach to the giant component problem.J. Combin. Theory Ser. B, 113:236–260, 2015

2015
[12]

Bourguin and G

S. Bourguin and G. Peccati. Portmanteau inequalities on the Poisson space: mixed regimes and multidimensional clustering.Electron. J. Probab., 19:no. 66, 42, 2014

2014
[13]

L. H. Y. Chen, L. Goldstein, and Q.-M. Shao.Normal approximation by Stein’s method. Probability and its Applications (New York). Springer, Heidelberg, 2011

2011
[14]

Chernozhukov, D

V. Chernozhukov, D. Chetverikov, and K. Kato. Comparison and anti-concentration bounds for maxima of Gaussian random vectors.Probab. Theory Related Fields, 162(1-2):47–70, 2015

2015
[15]

Fang and A

X. Fang and A. R¨ ollin. Rates of convergence for multivariate normal approximation with ap- plications to dense graphs and doubly indexed permutation statistics.Bernoulli, 21(4):2157– 2189, 2015

2015
[16]

B. K. Fosdick, D. B. Larremore, J. Nishimura, and J. Ugander. Configuring random graph models with fixed degree sequences.SIAM Rev., 60(2):315–355, 2018. 40 R. IMAI

2018
[17]

Goldstein and Y

L. Goldstein and Y. Rinott. Multivariate normal approximations by Stein’s method and size bias couplings.J. Appl. Probab., 33(1):1–17, 1996

1996
[18]

F. G¨ otze. On the rate of convergence in the multivariate CLT.Ann. Probab., 19(2):724–739, 1991

1991
[19]

van der Hofstad.Random graphs and complex networks

R. van der Hofstad.Random graphs and complex networks. Vol. 1, volume [43] ofCambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2017

2017
[20]

S. Janson. Coupling and Poisson approximation.Acta Appl. Math., 34(1-2):7–15, 1994

1994
[21]

S. Janson. The probability that a random multigraph is simple.Combin. Probab. Comput., 18(1-2):205–225, 2009

2009
[22]

S. Janson. Asymptotic equivalence and contiguity of some random graphs.Random Struc- tures Algorithms, 36(1):26–45, 2010

2010
[23]

S. Janson. The probability that a random multigraph is simple. II.J. Appl. Probab., 51A:123–137, 2014

2014
[24]

S. Janson. Asymptotic normality in random graphs with given vertex degrees.Random Structures Algorithms, 56(4):1070–1116, 2020

2020
[25]

S. Janson. Random graphs with given vertex degrees and switchings.Random Structures Algorithms, 57(1):3–31, 2020

2020
[26]

Janson and M

S. Janson and M. J. Luczak. A new approach to the giant component problem.Random Structures Algorithms, 34(2):197–216, 2009

2009
[27]

F. Joos, G. Perarnau, D. Rautenbach, and B. Reed. How to determine if a random graph with a fixed degree sequence has a giant component.Probab. Theory Related Fields, 170(1- 2):263–310, 2018

2018
[28]

High-dimensional Statistics for Stochastic Processes (Sep. 20-24, 2022 at Osaka U.)

Y. Koike. Lecture notes for “High-dimensional Statistics for Stochastic Processes (Sep. 20-24, 2022 at Osaka U.)” (in Japanese).Lecture notes available from the author’s website, May 2025

2022
[29]

Lang.Undergraduate analysis

S. Lang.Undergraduate analysis. Undergraduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1997

1997
[30]

E. Meckes. On Stein’s method for multivariate normal approximation. InHigh dimensional probability V: the Luminy volume, volume 5 ofInst. Math. Stat. (IMS) Collect., pages 153–178. Inst. Math. Statist., Beachwood, OH, 2009

2009
[31]

Molloy and B

M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random Structures Algorithms, 6(2-3):161–179, 1995

1995
[32]

Molloy and B

M. Molloy and B. Reed. The size of the giant component of a random graph with a given degree sequence.Combin. Probab. Comput., 7(3):295–305, 1998

1998
[33]

Nourdin and G

I. Nourdin and G. Peccati.Normal approximations with Malliavin calculus, volume 192 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2012. From Stein’s method to universality

2012
[34]

L. P. R. Pimentel. Integration by parts and the KPZ two-point function.Ann. Probab., 50(5):1755–1780, 2022

2022
[35]

M. Raiˇ c. A multivariate central limit theorem for Lipschitz and smooth test functions. arXiv e-prints, page arXiv:1812.08268v2, Jan. 2019

work page internal anchor Pith review Pith/arXiv arXiv 2019
[36]

M. Raiˇ c. A multivariate Berry-Esseen theorem with explicit constants.Bernoulli, 25(4A):2824–2853, 2019

2019
[37]

N. Ross. Fundamentals of Stein’s method.Probab. Surv., 8:210–293, 2011

2011
[38]

R. P. Stanley.Enumerative combinatorics. Volume 1, volume 49 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2012

2012
[39]

C. M. Stein. Estimation of the mean of a multivariate normal distribution.Ann. Statist., 9(6):1135–1151, 1981

1981
[40]

F. W. Steutel and K. van Harn. Discrete analogues of self-decomposability and stability. Ann. Probab., 7(5):893–899, 1979. NORMAL APPROXIMATION FOR ISOLATED EDGES AND 2-STARS IN UNIFORM SIMPLE GRAPHS 41

1979
[41]

Talagrand.Spin glasses: a challenge for mathematicians, volume 46 ofErgebnisse der Mathematik und ihrer Grenzgebiete

M. Talagrand.Spin glasses: a challenge for mathematicians, volume 46 ofErgebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics]. Springer-Verlag, Berlin, 2003. Cavity and mean field models

2003
[42]

Talagrand.Mean field models for spin glasses

M. Talagrand.Mean field models for spin glasses. Volume I, volume 54 ofErgebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics]. Springer-Verlag, Berlin, 2011. Basic examples

2011
[43]

C. A. Tudor. Multidimensional Stein method and quantitative asymptotic independence. Trans. Amer. Math. Soc., 378(2):1127–1165, 2025

2025
[44]

C. A. Tudor and J. Zurcher. Multidimensional Stein’s method for gamma approximation. ALEA Lat. Am. J. Probab. Math. Stat., 21(2):1709–1726, 2024

2024
[45]

C. A. Tudor and J. Zurcher. Multidimensional Stein-Malliavin calculus for the multivariate Gaussian distribution.Electron. J. Probab., 30:Paper No. 119, 28, 2025

2025
[46]

E[|Z jF(Z)|]<∞for all 1≤j≤d

C. A. Tudor and J. Zurcher. The spatial average of solutions to SPDEs is asymptotically independent of the solution.Bull. Sci. Math., 205:Paper No. 103719, 20, 2025. 42 R. IMAI AppendixA.Proof of(1.2) We adopt the following conventions: 1/(N−1)! ! = 1 and [N] =∅ifN= 0, and there is only one bijection from∅onto∅. Since each configuration is assigned probab...

2025
[47]

First note thatα∩α ′ =α∩(t 3t4) =α ′ ∩(t ′ 3t′
[48]

=∅. If (t 3t4)∩α ′ ̸=∅, thent 4 must be equal to eithers ′ 1 ors ′ 2 sincet 4, s′ 1, s′ 2 are incident to their degree 1 vertices andt 3 is incident to the degree 2 vertex, but thenα ′ andt 3t4 cannot coexist. Similarly, If (t ′ 3t′ 4)∩α̸=∅, thent ′ 4 must be equal to eithers 1 ors 2 sincet ′ 4, s1, s2 are incident to their degree 1 vertices andt ′ 3 is i...
[49]

First consider Case (b1i):{t 3, t4} ∩ {t′ 3, t′ 4}=∅

must hold. First consider Case (b1i):{t 3, t4} ∩ {t′ 3, t′ 4}=∅. Thenh α,α′,β,β ′ is a surjection fromG α ∩ Gα′ ∩ Gt3t4 ∩ G t′ 3t′ 4 ontoH α,α′,β,β ′. Indeed, for any (g β, gβ′)∈ H α,α′,β,β ′, lettingg := f −1 α (gβ) 1 = f −1 α′ (gβ′) 1 ∈ G α ∩ Gα′ ∩ Gt3t4 ∩ Gt′ 3t′ 4 yieldsh α,α′,β,β ′(g) = (gβ, gβ′). Therefore, Hα,α′,β,β ′ ≤ Gα ∩ Gα′ ∩ Gt3t4 ∩ Gt′ 3t′ 4...
[50]

First note thatα∩α ′ =α∩(t 3t4) =α ′ ∩(t′ 2t′
[51]

=∅. If (t 3t4)∩α ′ ̸=∅,t 4 must be equal to either s′ 1 ors ′ 2 sincet 4, s′ 1, s′ 2 are incident to their degree 1 vertices andt 3 is incident to the degree 2 vertex, but thent 3t4 andα ′ cannot coexist. Similarly, if (t3t4)∩(t ′ 2t′ 3)̸=∅, thent 3 must be equal to eithert ′ 2 ort ′ 3 becauset 3 is incident toβ’s degree 2 vertex,t ′ 2 ̸=t ′ 3 are inciden...
[52]

Sinceα, α ′, t3t4, t′ 2t′ 3 are now all disjoint,h α,α′,β,β ′ is a surjection fromG α ∩ Gα′ ∩ Gt3t4 ∩ Gt′ 2t′ 3 ontoH α,α′,β,β ′

=∅, since otherwiseH α,α′,β,β ′ will be empty. Sinceα, α ′, t3t4, t′ 2t′ 3 are now all disjoint,h α,α′,β,β ′ is a surjection fromG α ∩ Gα′ ∩ Gt3t4 ∩ Gt′ 2t′ 3 ontoH α,α′,β,β ′. Indeed, for any (g β, gβ′)∈ H α,α′,β,β ′, lettingg := f −1 α (gβ) 1 = f −1 α′ (gβ′) 1 ∈ Gα ∩ Gα′ ∩ Gt3t4 ∩ Gt′ 2t′ 3 yieldsh α,α′,β,β ′(g) = (gβ, gβ′). Therefore, we have Hα,α′,β,β...
[53]

First note thatα∩α ′ =α∩(t 2t3) =α ′ ∩(t ′ 2t′
[54]

Either Case (b4i): {t2, t3} ∩ {t′ 2, t′ 3}=∅or Case (b4ii):{t 2, t3} ∩ {t′ 2, t′ 3} ̸=∅happens

=α ′ ∩(t 2t3) =∅. Either Case (b4i): {t2, t3} ∩ {t′ 2, t′ 3}=∅or Case (b4ii):{t 2, t3} ∩ {t′ 2, t′ 3} ̸=∅happens. First consider Case (b4i):{t 2, t3} ∩ {t ′ 2, t′ 3}=∅. Then (t 2t3)∩(t ′ 2t′
[55]

Indeed, for any (g β, gβ′)∈ H α,α′,β,β ′, lettingg := f −1 α (gβ) 1 = f −1 α′ (gβ′) 1 ∈ G α ∩ Gα′ ∩ Gt2t3 ∩ Gt′ 2t′ 3 yieldsh α,α′,β,β ′(g) = (g β, gβ′)

=∅andh α,α′,β,β ′ is a surjection fromG α ∩ G α′ ∩ G t2t3 ∩ G t′ 2t′ 3 ontoH α,α′,β,β ′. Indeed, for any (g β, gβ′)∈ H α,α′,β,β ′, lettingg := f −1 α (gβ) 1 = f −1 α′ (gβ′) 1 ∈ G α ∩ Gα′ ∩ Gt2t3 ∩ Gt′ 2t′ 3 yieldsh α,α′,β,β ′(g) = (g β, gβ′). Therefore, we have Hα,α′,β,β ′ ≤ Gα ∩ Gα′ ∩ Gt2t3 ∩ Gt′ 2t′ 3 = (N−9)! ! and P(Iα =I α′ = 1, Jβα =J β′α′ = 1)≤ 1 (...
[56]

We have Hα,α′,β,β ′ ≤ |G α ∩ Gα′ ∩ Gt2t3|= (N−7)! ! and P(Iα =I α′ = 1, Jβα =J β′α′ = 1)≤ 1 ((N−1)) 3 1 (N−1) 2 in this case

holds.h α,α′,β,β ′ similarly defines a surjection fromG α ∩ Gα′ ∩ Gt2t3 ontoH α,α′,β,β ′. We have Hα,α′,β,β ′ ≤ |G α ∩ Gα′ ∩ Gt2t3|= (N−7)! ! and P(Iα =I α′ = 1, Jβα =J β′α′ = 1)≤ 1 ((N−1)) 3 1 (N−1) 2 in this case. The two degree 1 vertices ofβ ′ are those ofα ′. Since{t 2, t3}={t ′ 2, t′ 3}, the degree 2 vertex ofβ ′ is that ofβin this case. Therefore, ...
[57]

can happen. NORMAL APPROXIMATION FOR ISOLATED EDGES AND 2-STARS IN UNIFORM SIMPLE GRAPHS 67 From Cases (b1)–(b4), we conclude that X α,α′∈Γ11 α∩α′=∅ X β∈Γ12\{α} β∩α̸=∅ X β′∈Γ12\{α′} β′∩α′̸=∅ E IαIα′JβαJβ′α′ − X α,α′∈Γ11 α∩α′=∅ X β∈Γ12\{α} β∩α̸=∅ X β′∈Γ12\{α′} β′∩α′̸=∅ pαpα′pβpβ′ ≤ 32((n1)2)2n12n22 ((N−1)) 4(N−1) 2(N−3) + 4((n1)2)2n1n2 ((N−1)) 3(N−1) 2 | {...
[58]

In view of Lemma C.9, there are four possible cases in total aboutα∩β̸=∅, α̸=βand α′ ∩β ′ ̸=∅, α ′ ̸=β ′

andβ ′ = (t′ 1t′ 2)∪(t ′ 3t′ 4), where s2 ands 3 are incident toα’s degree 2 vertex,t 2 andt 3 are incident toβ’s degree 2 vertex,s ′ 2 ands ′ 3 are incident toα ′’s degree 2 vertex, andt ′ 2 andt ′ 3 are incident toβ ′’s degree 2 vertex. In view of Lemma C.9, there are four possible cases in total aboutα∩β̸=∅, α̸=βand α′ ∩β ′ ̸=∅, α ′ ̸=β ′. We begin wit...
[59]

Note that α∩α ′ =α∩(t 3t4) =α ′ ∩(t ′ 3t′
[60]

If (t3t4)∩α ′ ̸=∅,t 3t4 andα ′ must share a vertex

=∅. If (t3t4)∩α ′ ̸=∅,t 3t4 andα ′ must share a vertex. Whent 3t4 andα ′ share a degree 1 vertex,t 4 must be equal to eithers ′ 1 ors ′
[62]

To sum up, if (t 3t4)∩α ′ ̸=∅, we may assume thatt 3t4 coincides with an edge ofα ′, and then (t3t4)∩(t ′ 3t′

In the case whent 3 =s ′ 2 (resp.t 3 =s ′ 3), we may assume thatt 4 =s ′ 1 and t3t4 =s ′ 1s′ 2 (resp.t 4 =s ′ 4 andt 3t4 =s ′ 3s′ 4), because otherwiset 3t4 andα ′ cannot coexist and Hα,α′,β,β ′ will be empty. To sum up, if (t 3t4)∩α ′ ̸=∅, we may assume thatt 3t4 coincides with an edge ofα ′, and then (t3t4)∩(t ′ 3t′
[63]

=∅follows byα ′ ∩(t ′ 3t′
[64]

Similarly, if (t ′ 3t′ 4)∩α̸=∅, we may assume thatt ′ 3t′ 4 coincides with an edge ofα, and then (t 3t4)∩(t ′ 3t′

=∅. Similarly, if (t ′ 3t′ 4)∩α̸=∅, we may assume thatt ′ 3t′ 4 coincides with an edge ofα, and then (t 3t4)∩(t ′ 3t′
[65]

=∅follows by α∩(t 3t4) =∅. If{t 3, t4} ∩ {t′ 3, t′ 4} ̸=∅, we may assume that{t 3, t4}={t ′ 3, t′ 4}(and thust 3t4 =t ′ 3t′ 4), because otherwiset 3t4 andt ′ 3t′ 4 cannot coexist andH α,α′,β,β ′ will be empty. NORMAL APPROXIMATION FOR ISOLATED EDGES AND 2-STARS IN UNIFORM SIMPLE GRAPHS 69 From these observations, we realize that it suffices to consider th...
[66]

Whent 3t4 andα ′ share a degree 2 vertex,t 3 must be equal to eithers ′ 2 ors ′

In the case whent 4 =s ′ 1 (resp.t 4 =s ′ 4), we may assume that t3 =s ′ 2 andt 3t4 =s ′ 1s′ 2 (resp.t 3 =s ′ 3 andt 3t4 =s ′ 3s′ 4), because otherwiset 3t4 andα ′ cannot coexist andH α,α′,β,β ′ will be empty. Whent 3t4 andα ′ share a degree 2 vertex,t 3 must be equal to eithers ′ 2 ors ′
[67]

To sum up, if (t 3t4)∩α ′ ̸=∅, we may assume thatt 3t4 coincides with an edge ofα ′

In the case whent 3 =s ′ 2 (resp.t 3 =s ′ 3), we may assume thatt 4 =s ′ 1 and t3t4 =s ′ 1s′ 2 (resp.t 4 =s ′ 4 andt 3t4 =s ′ 3s′ 4), because otherwiset 3t4 andα ′ cannot coexist and Hα,α′,β,β ′ will be empty. To sum up, if (t 3t4)∩α ′ ̸=∅, we may assume thatt 3t4 coincides with an edge ofα ′. Thus it suffices to consider the following two subcases: Case ...
[68]

This shows thath α,β is a surjection ontoG β.□ D.2.5.Proof of Lemma C.7.(a) Letg∈ G α

Thus f −1 α (gβ) 2 =b 1 f −1 α (gβ) 1 andh α,β f −1 α (gβ) 1 =f α f −1 α (gβ) 1, f −1 α (gβ) 2 =g β. This shows thath α,β is a surjection ontoG β.□ D.2.5.Proof of Lemma C.7.(a) Letg∈ G α. Defineb 1 =b 1(g)∈[N−1] by b1(g) :=    the rank of the partner oft 2 ing among theN−1 half-edges other thans 1 (s1 < s2) the rank oft 2 among theN−1 half-edges other ...
[69]

This shows thath α,β is a surjection from Gα ∩ Gt3t4 ontoG β

Thus f −1 α (gβ) 2 =b 1 f −1 α (gβ) 1 and hα,β f −1 α (gβ) 1 =f α f −1 α (gβ) 1, f −1 α (gβ) 2 =g β. This shows thath α,β is a surjection from Gα ∩ Gt3t4 ontoG β. 90 R. IMAI (b) Letg∈ G α. Defineb 1 ∈[N−1] by b1 := ( the rank oft 2 among theN−1 half-edges other thans 1 (s1 < s2) the rank oft 3 among theN−1 half-edges other thans 2 (s2 < s1) . Then define ...
[70]

Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate of f −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2

Let f −1 α,2(gβ) 1 ∈ G α,1 =G s3s4 be the first coordinate off −1 α,2(gβ). Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate of f −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2 . Thenf α,1(g, b1) = f −1 α,2(gβ) 1 . The second coordinate off −1 α,2(gβ), f −1 α,2(gβ) 2 ∈[N−1], is the rank of the partner ofs 3 ∧s 4 ing β among theN−1 half-edges other t...
[71]

Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate off −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2

Let f −1 α,2(gβ) 1 ∈ G α,1 =G s3s4 be the first coordinate off −1 α,2(gβ). Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate off −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2 . Thenf α,1(g, b1) = f −1 α,2(gβ) 1 . The second coordinate off −1 α,2(gβ), f −1 α,2(gβ) 2 ∈[N−1], is the rank of the partner ofs 3 ∧s 4 ing β among theN−1 half-edges other th...
[72]

Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate of f −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2

Let f −1 α,2(gβ) 1 ∈ G α,1 =G s3s4 be the first coordinate off −1 α,2(gβ). Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate of f −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2 . Thenf α,1(g, b1) = f −1 α,2(gβ) 1 . The second coordinate off −1 α,2(gβ), f −1 α,2(gβ) 2 ∈[N−1], is the rank of the partner ofs 3 ∧s 4 ing β among theN−1 half-edges other t...

[1] [1]

W. J. Anderson.Continuous-time Markov chains. Springer Series in Statistics: Probability and its Applications. Springer-Verlag, New York, 1991. An applications-oriented approach

1991

[2] [2]

Angel, R

O. Angel, R. van der Hofstad, and C. Holmgren. Limit laws for self-loops and multiple edges in the configuration model.Ann. Inst. Henri Poincar´ e Probab. Stat., 55(3):1509–1530, 2019. [Author name corrected by publisher]

2019

[3] [3]

Arratia, L

R. Arratia, L. Goldstein, and L. Gordon. Two moments suffice for Poisson approximations: the Chen-Stein method.Ann. Probab., 17(1):9–25, 1989

1989

[4] [4]

Central limit theorem for statistics of subcritical configuration models

S. Athreya and D. Yogeshwaran. Central limit theorem for statistics of subcritical configu- ration models.arXiv e-prints, page arXiv:1808.06778, Aug. 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018

[5] [5]

Ball and P

F. Ball and P. Neal. The asymptotic variance of the giant component of configuration model random graphs.Ann. Appl. Probab., 27(2):1057–1092, 2017

2017

[6] [6]

A. D. Barbour. Stein’s method and Poisson process convergence.J. Appl. Probab., 25(A):175–184, 1988. A celebration of applied probability

1988

[7] [7]

A. D. Barbour. Multivariate Poisson-binomial approximation using Stein’s method. In Stein’s method and applications, volume 5 ofLect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., pages 131–142. Singapore Univ. Press, Singapore, 2005

2005

[8] [8]

A. D. Barbour, L. Holst, and S. Janson.Poisson approximation, volume 2 ofOxford Studies in Probability. The Clarendon Press, Oxford University Press, New York, 1992. Oxford Science Publications

1992

[9] [9]

A. D. Barbour and A. R¨ ollin. Central limit theorems in the configuration model.Ann. Appl. Probab., 29(2):1046–1069, 2019

2019

[10] [10]

Bollob´ as

B. Bollob´ as. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.European J. Combin., 1(4):311–316, 1980

1980

[11] [11]

Bollob´ as and O

B. Bollob´ as and O. Riordan. An old approach to the giant component problem.J. Combin. Theory Ser. B, 113:236–260, 2015

2015

[12] [12]

Bourguin and G

S. Bourguin and G. Peccati. Portmanteau inequalities on the Poisson space: mixed regimes and multidimensional clustering.Electron. J. Probab., 19:no. 66, 42, 2014

2014

[13] [13]

L. H. Y. Chen, L. Goldstein, and Q.-M. Shao.Normal approximation by Stein’s method. Probability and its Applications (New York). Springer, Heidelberg, 2011

2011

[14] [14]

Chernozhukov, D

V. Chernozhukov, D. Chetverikov, and K. Kato. Comparison and anti-concentration bounds for maxima of Gaussian random vectors.Probab. Theory Related Fields, 162(1-2):47–70, 2015

2015

[15] [15]

Fang and A

X. Fang and A. R¨ ollin. Rates of convergence for multivariate normal approximation with ap- plications to dense graphs and doubly indexed permutation statistics.Bernoulli, 21(4):2157– 2189, 2015

2015

[16] [16]

B. K. Fosdick, D. B. Larremore, J. Nishimura, and J. Ugander. Configuring random graph models with fixed degree sequences.SIAM Rev., 60(2):315–355, 2018. 40 R. IMAI

2018

[17] [17]

Goldstein and Y

L. Goldstein and Y. Rinott. Multivariate normal approximations by Stein’s method and size bias couplings.J. Appl. Probab., 33(1):1–17, 1996

1996

[18] [18]

F. G¨ otze. On the rate of convergence in the multivariate CLT.Ann. Probab., 19(2):724–739, 1991

1991

[19] [19]

van der Hofstad.Random graphs and complex networks

R. van der Hofstad.Random graphs and complex networks. Vol. 1, volume [43] ofCambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2017

2017

[20] [20]

S. Janson. Coupling and Poisson approximation.Acta Appl. Math., 34(1-2):7–15, 1994

1994

[21] [21]

S. Janson. The probability that a random multigraph is simple.Combin. Probab. Comput., 18(1-2):205–225, 2009

2009

[22] [22]

S. Janson. Asymptotic equivalence and contiguity of some random graphs.Random Struc- tures Algorithms, 36(1):26–45, 2010

2010

[23] [23]

S. Janson. The probability that a random multigraph is simple. II.J. Appl. Probab., 51A:123–137, 2014

2014

[24] [24]

S. Janson. Asymptotic normality in random graphs with given vertex degrees.Random Structures Algorithms, 56(4):1070–1116, 2020

2020

[25] [25]

S. Janson. Random graphs with given vertex degrees and switchings.Random Structures Algorithms, 57(1):3–31, 2020

2020

[26] [26]

Janson and M

S. Janson and M. J. Luczak. A new approach to the giant component problem.Random Structures Algorithms, 34(2):197–216, 2009

2009

[27] [27]

F. Joos, G. Perarnau, D. Rautenbach, and B. Reed. How to determine if a random graph with a fixed degree sequence has a giant component.Probab. Theory Related Fields, 170(1- 2):263–310, 2018

2018

[28] [28]

High-dimensional Statistics for Stochastic Processes (Sep. 20-24, 2022 at Osaka U.)

Y. Koike. Lecture notes for “High-dimensional Statistics for Stochastic Processes (Sep. 20-24, 2022 at Osaka U.)” (in Japanese).Lecture notes available from the author’s website, May 2025

2022

[29] [29]

Lang.Undergraduate analysis

S. Lang.Undergraduate analysis. Undergraduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1997

1997

[30] [30]

E. Meckes. On Stein’s method for multivariate normal approximation. InHigh dimensional probability V: the Luminy volume, volume 5 ofInst. Math. Stat. (IMS) Collect., pages 153–178. Inst. Math. Statist., Beachwood, OH, 2009

2009

[31] [31]

Molloy and B

M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random Structures Algorithms, 6(2-3):161–179, 1995

1995

[32] [32]

Molloy and B

M. Molloy and B. Reed. The size of the giant component of a random graph with a given degree sequence.Combin. Probab. Comput., 7(3):295–305, 1998

1998

[33] [33]

Nourdin and G

I. Nourdin and G. Peccati.Normal approximations with Malliavin calculus, volume 192 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2012. From Stein’s method to universality

2012

[34] [34]

L. P. R. Pimentel. Integration by parts and the KPZ two-point function.Ann. Probab., 50(5):1755–1780, 2022

2022

[35] [35]

M. Raiˇ c. A multivariate central limit theorem for Lipschitz and smooth test functions. arXiv e-prints, page arXiv:1812.08268v2, Jan. 2019

work page internal anchor Pith review Pith/arXiv arXiv 2019

[36] [36]

M. Raiˇ c. A multivariate Berry-Esseen theorem with explicit constants.Bernoulli, 25(4A):2824–2853, 2019

2019

[37] [37]

N. Ross. Fundamentals of Stein’s method.Probab. Surv., 8:210–293, 2011

2011

[38] [38]

R. P. Stanley.Enumerative combinatorics. Volume 1, volume 49 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2012

2012

[39] [39]

C. M. Stein. Estimation of the mean of a multivariate normal distribution.Ann. Statist., 9(6):1135–1151, 1981

1981

[40] [40]

F. W. Steutel and K. van Harn. Discrete analogues of self-decomposability and stability. Ann. Probab., 7(5):893–899, 1979. NORMAL APPROXIMATION FOR ISOLATED EDGES AND 2-STARS IN UNIFORM SIMPLE GRAPHS 41

1979

[41] [41]

Talagrand.Spin glasses: a challenge for mathematicians, volume 46 ofErgebnisse der Mathematik und ihrer Grenzgebiete

M. Talagrand.Spin glasses: a challenge for mathematicians, volume 46 ofErgebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics]. Springer-Verlag, Berlin, 2003. Cavity and mean field models

2003

[42] [42]

Talagrand.Mean field models for spin glasses

M. Talagrand.Mean field models for spin glasses. Volume I, volume 54 ofErgebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics]. Springer-Verlag, Berlin, 2011. Basic examples

2011

[43] [43]

C. A. Tudor. Multidimensional Stein method and quantitative asymptotic independence. Trans. Amer. Math. Soc., 378(2):1127–1165, 2025

2025

[44] [44]

C. A. Tudor and J. Zurcher. Multidimensional Stein’s method for gamma approximation. ALEA Lat. Am. J. Probab. Math. Stat., 21(2):1709–1726, 2024

2024

[45] [45]

C. A. Tudor and J. Zurcher. Multidimensional Stein-Malliavin calculus for the multivariate Gaussian distribution.Electron. J. Probab., 30:Paper No. 119, 28, 2025

2025

[46] [46]

E[|Z jF(Z)|]<∞for all 1≤j≤d

C. A. Tudor and J. Zurcher. The spatial average of solutions to SPDEs is asymptotically independent of the solution.Bull. Sci. Math., 205:Paper No. 103719, 20, 2025. 42 R. IMAI AppendixA.Proof of(1.2) We adopt the following conventions: 1/(N−1)! ! = 1 and [N] =∅ifN= 0, and there is only one bijection from∅onto∅. Since each configuration is assigned probab...

2025

[47] [47]

First note thatα∩α ′ =α∩(t 3t4) =α ′ ∩(t ′ 3t′

[48] [48]

=∅. If (t 3t4)∩α ′ ̸=∅, thent 4 must be equal to eithers ′ 1 ors ′ 2 sincet 4, s′ 1, s′ 2 are incident to their degree 1 vertices andt 3 is incident to the degree 2 vertex, but thenα ′ andt 3t4 cannot coexist. Similarly, If (t ′ 3t′ 4)∩α̸=∅, thent ′ 4 must be equal to eithers 1 ors 2 sincet ′ 4, s1, s2 are incident to their degree 1 vertices andt ′ 3 is i...

[49] [49]

First consider Case (b1i):{t 3, t4} ∩ {t′ 3, t′ 4}=∅

must hold. First consider Case (b1i):{t 3, t4} ∩ {t′ 3, t′ 4}=∅. Thenh α,α′,β,β ′ is a surjection fromG α ∩ Gα′ ∩ Gt3t4 ∩ G t′ 3t′ 4 ontoH α,α′,β,β ′. Indeed, for any (g β, gβ′)∈ H α,α′,β,β ′, lettingg := f −1 α (gβ) 1 = f −1 α′ (gβ′) 1 ∈ G α ∩ Gα′ ∩ Gt3t4 ∩ Gt′ 3t′ 4 yieldsh α,α′,β,β ′(g) = (gβ, gβ′). Therefore, Hα,α′,β,β ′ ≤ Gα ∩ Gα′ ∩ Gt3t4 ∩ Gt′ 3t′ 4...

[50] [50]

First note thatα∩α ′ =α∩(t 3t4) =α ′ ∩(t′ 2t′

[51] [51]

=∅. If (t 3t4)∩α ′ ̸=∅,t 4 must be equal to either s′ 1 ors ′ 2 sincet 4, s′ 1, s′ 2 are incident to their degree 1 vertices andt 3 is incident to the degree 2 vertex, but thent 3t4 andα ′ cannot coexist. Similarly, if (t3t4)∩(t ′ 2t′ 3)̸=∅, thent 3 must be equal to eithert ′ 2 ort ′ 3 becauset 3 is incident toβ’s degree 2 vertex,t ′ 2 ̸=t ′ 3 are inciden...

[52] [52]

Sinceα, α ′, t3t4, t′ 2t′ 3 are now all disjoint,h α,α′,β,β ′ is a surjection fromG α ∩ Gα′ ∩ Gt3t4 ∩ Gt′ 2t′ 3 ontoH α,α′,β,β ′

=∅, since otherwiseH α,α′,β,β ′ will be empty. Sinceα, α ′, t3t4, t′ 2t′ 3 are now all disjoint,h α,α′,β,β ′ is a surjection fromG α ∩ Gα′ ∩ Gt3t4 ∩ Gt′ 2t′ 3 ontoH α,α′,β,β ′. Indeed, for any (g β, gβ′)∈ H α,α′,β,β ′, lettingg := f −1 α (gβ) 1 = f −1 α′ (gβ′) 1 ∈ Gα ∩ Gα′ ∩ Gt3t4 ∩ Gt′ 2t′ 3 yieldsh α,α′,β,β ′(g) = (gβ, gβ′). Therefore, we have Hα,α′,β,β...

[53] [53]

First note thatα∩α ′ =α∩(t 2t3) =α ′ ∩(t ′ 2t′

[54] [54]

Either Case (b4i): {t2, t3} ∩ {t′ 2, t′ 3}=∅or Case (b4ii):{t 2, t3} ∩ {t′ 2, t′ 3} ̸=∅happens

=α ′ ∩(t 2t3) =∅. Either Case (b4i): {t2, t3} ∩ {t′ 2, t′ 3}=∅or Case (b4ii):{t 2, t3} ∩ {t′ 2, t′ 3} ̸=∅happens. First consider Case (b4i):{t 2, t3} ∩ {t ′ 2, t′ 3}=∅. Then (t 2t3)∩(t ′ 2t′

[55] [55]

Indeed, for any (g β, gβ′)∈ H α,α′,β,β ′, lettingg := f −1 α (gβ) 1 = f −1 α′ (gβ′) 1 ∈ G α ∩ Gα′ ∩ Gt2t3 ∩ Gt′ 2t′ 3 yieldsh α,α′,β,β ′(g) = (g β, gβ′)

=∅andh α,α′,β,β ′ is a surjection fromG α ∩ G α′ ∩ G t2t3 ∩ G t′ 2t′ 3 ontoH α,α′,β,β ′. Indeed, for any (g β, gβ′)∈ H α,α′,β,β ′, lettingg := f −1 α (gβ) 1 = f −1 α′ (gβ′) 1 ∈ G α ∩ Gα′ ∩ Gt2t3 ∩ Gt′ 2t′ 3 yieldsh α,α′,β,β ′(g) = (g β, gβ′). Therefore, we have Hα,α′,β,β ′ ≤ Gα ∩ Gα′ ∩ Gt2t3 ∩ Gt′ 2t′ 3 = (N−9)! ! and P(Iα =I α′ = 1, Jβα =J β′α′ = 1)≤ 1 (...

[56] [56]

We have Hα,α′,β,β ′ ≤ |G α ∩ Gα′ ∩ Gt2t3|= (N−7)! ! and P(Iα =I α′ = 1, Jβα =J β′α′ = 1)≤ 1 ((N−1)) 3 1 (N−1) 2 in this case

holds.h α,α′,β,β ′ similarly defines a surjection fromG α ∩ Gα′ ∩ Gt2t3 ontoH α,α′,β,β ′. We have Hα,α′,β,β ′ ≤ |G α ∩ Gα′ ∩ Gt2t3|= (N−7)! ! and P(Iα =I α′ = 1, Jβα =J β′α′ = 1)≤ 1 ((N−1)) 3 1 (N−1) 2 in this case. The two degree 1 vertices ofβ ′ are those ofα ′. Since{t 2, t3}={t ′ 2, t′ 3}, the degree 2 vertex ofβ ′ is that ofβin this case. Therefore, ...

[57] [57]

can happen. NORMAL APPROXIMATION FOR ISOLATED EDGES AND 2-STARS IN UNIFORM SIMPLE GRAPHS 67 From Cases (b1)–(b4), we conclude that X α,α′∈Γ11 α∩α′=∅ X β∈Γ12\{α} β∩α̸=∅ X β′∈Γ12\{α′} β′∩α′̸=∅ E IαIα′JβαJβ′α′ − X α,α′∈Γ11 α∩α′=∅ X β∈Γ12\{α} β∩α̸=∅ X β′∈Γ12\{α′} β′∩α′̸=∅ pαpα′pβpβ′ ≤ 32((n1)2)2n12n22 ((N−1)) 4(N−1) 2(N−3) + 4((n1)2)2n1n2 ((N−1)) 3(N−1) 2 | {...

[58] [58]

In view of Lemma C.9, there are four possible cases in total aboutα∩β̸=∅, α̸=βand α′ ∩β ′ ̸=∅, α ′ ̸=β ′

andβ ′ = (t′ 1t′ 2)∪(t ′ 3t′ 4), where s2 ands 3 are incident toα’s degree 2 vertex,t 2 andt 3 are incident toβ’s degree 2 vertex,s ′ 2 ands ′ 3 are incident toα ′’s degree 2 vertex, andt ′ 2 andt ′ 3 are incident toβ ′’s degree 2 vertex. In view of Lemma C.9, there are four possible cases in total aboutα∩β̸=∅, α̸=βand α′ ∩β ′ ̸=∅, α ′ ̸=β ′. We begin wit...

[59] [59]

Note that α∩α ′ =α∩(t 3t4) =α ′ ∩(t ′ 3t′

[60] [60]

If (t3t4)∩α ′ ̸=∅,t 3t4 andα ′ must share a vertex

=∅. If (t3t4)∩α ′ ̸=∅,t 3t4 andα ′ must share a vertex. Whent 3t4 andα ′ share a degree 1 vertex,t 4 must be equal to eithers ′ 1 ors ′

[61] [62]

To sum up, if (t 3t4)∩α ′ ̸=∅, we may assume thatt 3t4 coincides with an edge ofα ′, and then (t3t4)∩(t ′ 3t′

In the case whent 3 =s ′ 2 (resp.t 3 =s ′ 3), we may assume thatt 4 =s ′ 1 and t3t4 =s ′ 1s′ 2 (resp.t 4 =s ′ 4 andt 3t4 =s ′ 3s′ 4), because otherwiset 3t4 andα ′ cannot coexist and Hα,α′,β,β ′ will be empty. To sum up, if (t 3t4)∩α ′ ̸=∅, we may assume thatt 3t4 coincides with an edge ofα ′, and then (t3t4)∩(t ′ 3t′

[62] [63]

=∅follows byα ′ ∩(t ′ 3t′

[63] [64]

Similarly, if (t ′ 3t′ 4)∩α̸=∅, we may assume thatt ′ 3t′ 4 coincides with an edge ofα, and then (t 3t4)∩(t ′ 3t′

=∅. Similarly, if (t ′ 3t′ 4)∩α̸=∅, we may assume thatt ′ 3t′ 4 coincides with an edge ofα, and then (t 3t4)∩(t ′ 3t′

[64] [65]

=∅follows by α∩(t 3t4) =∅. If{t 3, t4} ∩ {t′ 3, t′ 4} ̸=∅, we may assume that{t 3, t4}={t ′ 3, t′ 4}(and thust 3t4 =t ′ 3t′ 4), because otherwiset 3t4 andt ′ 3t′ 4 cannot coexist andH α,α′,β,β ′ will be empty. NORMAL APPROXIMATION FOR ISOLATED EDGES AND 2-STARS IN UNIFORM SIMPLE GRAPHS 69 From these observations, we realize that it suffices to consider th...

[65] [66]

Whent 3t4 andα ′ share a degree 2 vertex,t 3 must be equal to eithers ′ 2 ors ′

In the case whent 4 =s ′ 1 (resp.t 4 =s ′ 4), we may assume that t3 =s ′ 2 andt 3t4 =s ′ 1s′ 2 (resp.t 3 =s ′ 3 andt 3t4 =s ′ 3s′ 4), because otherwiset 3t4 andα ′ cannot coexist andH α,α′,β,β ′ will be empty. Whent 3t4 andα ′ share a degree 2 vertex,t 3 must be equal to eithers ′ 2 ors ′

[66] [67]

To sum up, if (t 3t4)∩α ′ ̸=∅, we may assume thatt 3t4 coincides with an edge ofα ′

In the case whent 3 =s ′ 2 (resp.t 3 =s ′ 3), we may assume thatt 4 =s ′ 1 and t3t4 =s ′ 1s′ 2 (resp.t 4 =s ′ 4 andt 3t4 =s ′ 3s′ 4), because otherwiset 3t4 andα ′ cannot coexist and Hα,α′,β,β ′ will be empty. To sum up, if (t 3t4)∩α ′ ̸=∅, we may assume thatt 3t4 coincides with an edge ofα ′. Thus it suffices to consider the following two subcases: Case ...

[67] [68]

This shows thath α,β is a surjection ontoG β.□ D.2.5.Proof of Lemma C.7.(a) Letg∈ G α

Thus f −1 α (gβ) 2 =b 1 f −1 α (gβ) 1 andh α,β f −1 α (gβ) 1 =f α f −1 α (gβ) 1, f −1 α (gβ) 2 =g β. This shows thath α,β is a surjection ontoG β.□ D.2.5.Proof of Lemma C.7.(a) Letg∈ G α. Defineb 1 =b 1(g)∈[N−1] by b1(g) :=    the rank of the partner oft 2 ing among theN−1 half-edges other thans 1 (s1 < s2) the rank oft 2 among theN−1 half-edges other ...

[68] [69]

This shows thath α,β is a surjection from Gα ∩ Gt3t4 ontoG β

Thus f −1 α (gβ) 2 =b 1 f −1 α (gβ) 1 and hα,β f −1 α (gβ) 1 =f α f −1 α (gβ) 1, f −1 α (gβ) 2 =g β. This shows thath α,β is a surjection from Gα ∩ Gt3t4 ontoG β. 90 R. IMAI (b) Letg∈ G α. Defineb 1 ∈[N−1] by b1 := ( the rank oft 2 among theN−1 half-edges other thans 1 (s1 < s2) the rank oft 3 among theN−1 half-edges other thans 2 (s2 < s1) . Then define ...

[69] [70]

Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate of f −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2

Let f −1 α,2(gβ) 1 ∈ G α,1 =G s3s4 be the first coordinate off −1 α,2(gβ). Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate of f −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2 . Thenf α,1(g, b1) = f −1 α,2(gβ) 1 . The second coordinate off −1 α,2(gβ), f −1 α,2(gβ) 2 ∈[N−1], is the rank of the partner ofs 3 ∧s 4 ing β among theN−1 half-edges other t...

[70] [71]

Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate off −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2

Let f −1 α,2(gβ) 1 ∈ G α,1 =G s3s4 be the first coordinate off −1 α,2(gβ). Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate off −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2 . Thenf α,1(g, b1) = f −1 α,2(gβ) 1 . The second coordinate off −1 α,2(gβ), f −1 α,2(gβ) 2 ∈[N−1], is the rank of the partner ofs 3 ∧s 4 ing β among theN−1 half-edges other th...

[71] [72]

Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate of f −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2

Let f −1 α,2(gβ) 1 ∈ G α,1 =G s3s4 be the first coordinate off −1 α,2(gβ). Takeb 1 =b 1(gβ)∈[N−3] as the second coordinate of f −1 α,1 f −1 α,2(gβ) 1 , b1 = f −1 α,1 f −1 α,2(gβ) 1 2 . Thenf α,1(g, b1) = f −1 α,2(gβ) 1 . The second coordinate off −1 α,2(gβ), f −1 α,2(gβ) 2 ∈[N−1], is the rank of the partner ofs 3 ∧s 4 ing β among theN−1 half-edges other t...