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

Recognition: 2 theorem links

· Lean Theorem

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

Ryo Imai

Authors on Pith no claims yet

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.

Reference graph

Works this paper leans on

71 extracted references · 71 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

work page 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]

work page 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

work page 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

work page 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

work page 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

work page 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

work page 1992
[9]

A. D. Barbour and A. R¨ ollin. Central limit theorems in the configuration model.Ann. Appl. Probab., 29(2):1046–1069, 2019. NORMAL APPROXIMATION FOR ISOLATED EDGES AND 2-STARS IN UNIFORM SIMPLE GRAPHS 39

work page 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

work page 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

work page 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

work page 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

work page 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

work page 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

work page 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

work page 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

work page 1996
[18]

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

work page 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

work page 2017
[20]

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

work page 1994
[21]

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

work page 2009
[22]

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

work page 2010
[23]

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

work page 2014
[24]

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

work page 2020
[25]

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

work page 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

work page 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

work page 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

work page 2022
[29]

Lang.Undergraduate analysis

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

work page 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

work page 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

work page 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. 40 R. IMAI

work page 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

work page 2012
[34]

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

work page 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

work page 2019
[37]

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

work page 2011
[38]

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

work page 2012
[39]

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

work page 1981
[40]

F. W. Steutel and K. van Harn. Discrete analogues of self-decomposability and stability. Ann. Probab., 7(5):893–899, 1979

work page 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

work page 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

work page 2011
[43]

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

work page 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

work page 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

work page 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. NORMAL APPROXIMATION FOR ISOLATED EDGES AND 2-STARS IN UNIFORM SIMPLE GRAPHS 41 Supplementary Material AppendixA.Proof of(2) We adopt the following conventions: 1/(N−1)! ! = 1 and [N] =∅ifN= ...

work page 2025
[47]

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

work page
[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...

work page
[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...

work page
[50]

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

work page
[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...

work page
[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α,α′,β,β...

work page
[53]

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

work page
[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′

work page
[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 (...

work page
[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, ...

work page
[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 | {...

work page
[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...

work page
[59]

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

work page
[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 ′

work page
[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′

work page
[63]

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

work page
[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′

work page
[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...

work page
[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 ′

work page
[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 ...

work page
[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 ...

work page
[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 ...

work page
[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...

work page
[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...

work page
[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...

work page