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

Abstract

We consider the configuration model and the uniform simple graph with given degree sequence $\mathbf{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.

arXiv commentmain text 41 pages + appendix 59 pages; a minor issue in Section 4.2.3 fixed