Normal approximation for subgraph counts in random intersection graphs: the case of edges

Katarzyna Rybarczyk, Grzegorz Serafin · 2025

Read Normal approximation for subgraph counts in random intersection graphs: the case of edges by Katarzyna Rybarczyk, Grzegorz Serafin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23110.txt.

Introduction

Katarzyna Rybarczyk and Grzegorz Serafin prove bell-curve bounds for counts inside a random graph built from shared sets. Their 2025 paper studies intersection graphs, where points link when their sets overlap. Shared sets make links lean on each other, so counts behave less neatly than in the classic random graph. The pair works with a broad family of count statistics that includes small pattern counts.

Their bounds hold under two standard measures of closeness to a bell curve. The team then shows how the bounds apply to counts of small patterns in the graph. Edge count serves as the worked case. For edges, they give exact terms for when the count settles into a bell-curve shape as the graph grows. The results give later workers a firm base for harder patterns in the same model.

Catalog record

CREATORKatarzyna Rybarczyk, Grzegorz Serafin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE130 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-23110

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Normal approximation for subgraph counts in random intersection graphs: the case of edges Katarzyna Rybarczyk, Grzegorz Serafin Abstract We investigate the subgraph count in the random intersection graph model 𝒢 ⁡ ( n ​ ; ​ m ​ ; ​ p ) \mathcal{G}(n\mathord{\mathchar 59\relax}m\mathord{\mathchar 59\relax}p) . Due to substantial edge dependencies, studying even such fundamental statistics is significantly more challenging than in the classical binomial model 𝒢 ⁡ ( n ​ ; ​ p ) \mathcal{G}(n\mathord{\mathchar 59\relax}p) . This article establish new normal approximation bounds in both the Wasserstein and Kolmogorov distances for general non-degenerate U U -statistics. We then illustrate how these results can be potentially applied to the standardized number of subgraphs in the random intersection graph model. Finally, as a basic example, we derive necessary and sufficient conditions for the asymptotic normality of the number of edges in 𝒢 ⁡ ( n ​ ; ​ m ​ ; ​ p ) \mathcal{G}(n\mathord{\mathchar 59\relax}m\mathord{\mathchar 59\relax}p) . Keywords : random intersection graph, subgraph count, normal approximation, convergence rates. MSC2020 subject classification : Primary 05C80, 60F05; Secondary 05C82. 1 Introduction Counting small subgraphs is one of the fundamental problems in the study of random graphs. In particular, it plays a crucial role in the research on the classical {\mathcal{G}}(n\mathchar 59\relax p) model (see [ 1 , 20 ] and references therein) and still attracts a significant interest [ 12 , 18 , 22 , 24 , 31 ] . The long standing problem of normal approximation bounds in Kolmogorov distance has been resolved just recently [ 31 ] , see also [ 18 , 34 , 42 ] for different approaches. In this article, we address the small subgraph count in the random intersection graph model {\mathcal{G}}(n\mathchar 59\relax m\mathchar 59\relax p) , that was introduced by Karoński, Scheinerman and Singer–Cohen in [ 26 ] . Unlike the classical binomial Erdős–Rényi random graph, {\mathcal{G}}(n\mathchar 59\relax m\mathchar 59\relax p) exhibits strong dependencies between edges, which is manifested by high density of cliques. This abundance of cliques, along with the edge correlations and other structural properties of random intersection graphs have resulted in the model and its generalisations finding many applications such as: “gate matrix layout” for VLSI design [ 26 ] , cluster analysis and classification [ 21 ] , analysis of complex networks [ 3 , 14 ] , secure wireless networks [ 7 ] or epidemics [ 10 ] . For more details, we refer the reader to the survey papers [ 4 , 5 , 41 ] . Due to the edge dependencies, studying random intersection graph in the context of small subgraphs turns out to be much more challenging comparing to the binomial model. Even the analysis of the distribution of the number of edges in {\mathcal{G}}(n\mathchar 59\relax m\mathchar 59\relax p) is non-trivial, whereas in the {\mathcal{G}}(n\mathchar 59\relax p) model the number of edges follows a simple binomial distribution. This complexity of the model has been already revealed in the form of thresholds for existence of at least one copy of a given graph [ 26 ] . Concerning further results in this direction, the distribution of the number of copies of small subgraphs in {\mathcal{G}}(n\mathchar 59\relax m\mathchar 59\relax p) on the threshold was studied in [ 39 ] and [ 40 ] . For some related random intersection graph models in various ranges of parameters a normal approximation of the number of triangles [ 6 ] and 2–connected subgraphs [ 8 ] was determined. However, none of the methods used in these works could be adopted to determine conditions for asymptotic normality of the number of small cliques in {\mathcal{G}}(n\mathchar 59\relax m\mathchar 59\relax p) . Only recently some results concerning the normal distribution of the number of triangles in a random intersection graph have been proved by Dong and Hu [ 17 ] . They employed the Stein method to find an upper bound on the Kolmogorov distance between standardised random variable counting the number of triangles in {\mathcal{G}}(n\mathchar 59\relax m\mathchar 59\relax p) and the standard normal distribution. Although [ 17 ] is a substantial contribution to the solution of the problem, it covers only a part of the range of parameters. First of all, it concerns only sparse graphs (in which edge probability tends to zero). Secondly, for a significant range of the parameters n\mathchar 59\relax m\mathchar 59\relax p , the obtained upper bound does not tend to zero, while asymptotic normality is expected. In particular, this concerns the case when m\geq n^{2} , which is counterintuitive, as the larger m is, the more {\mathcal{G}}(n\mathchar 59\relax m\mathchar 59\relax p) resembles an Erdős–Rényi graph, as discussed in [ 19 ] . Furthermore, a long line of research has shown that for m\gg n^{3} the graph {\mathcal{G}}(n\mathchar 59\relax m\mathchar 59\relax p) and Erdős–Rényi graph with the edge probability close to 1-(1-p^{2})^{m} are asymptotically equivalent [ 19 , 36 , 27 , 9 ] . The aim of this paper is to develop a new, more efficient method for finding an upper bound on the distance between a standardised random variable counting the number of small subgraphs in \mathcal{G}(n\mathchar 59\relax m\mathchar 59\relax p) and the standard normal distribution. We achieved this by developing and combining some probabilistic as well as combinatorial techniques. The probabilistic ingredient of the approach builds on ideas from [ 31 , 32 , 33 ] , where the Stein method was combined with Malliavin calculus to obtain normal approximation bounds for functionals of independent random variables distributed uniformly on the interval (-1\mathchar 59\relax 1) . These methods have been already used in the context of small subgraphs in other random graph models [ 28 , 31 , 32 ] ; however, they are not directly applicable to the \mathcal{G}(n\mathchar 59\relax m\mathchar 59\relax p) model due to the aforementioned edge dependencies. For this reason, in Theorem 2.1 we derive a new bound that applies not only to the subgraph count in {\mathcal{G}}(n\mathchar 59\relax m\mathchar 59\relax p) , but to general U -statistics of random vectors. On the other hand, what is essential for establishing accurate estimates of the distance, is the estimation of the central moments of subgraphs existence indicators. We believe that omitting centralization was one of the reasons for the gap in the result from [ 17 ] . We resolve this problem by very subtle analysis of so called clique covers, that were introduced in [ 26 ] and describe subgraphs existence conditions. Namely, we developed new techniques for comparing clique covers of two not necessarily isomorphic graphs. This allows us to estimate specific types of central moments that are crucial for the final results. Additionally, the probabilistic approach described above effectively limits the number of cases considered. Namely, analyzing the higher central moments of a random variable counting the number of edges in {\mathcal{G}}(n\mathchar 59\relax m\mathchar 59\relax p) poses a significant challenge and requires a thorough examination of clique covers of certain subgraphs associated with these moments. Theorem 2.1 greatly simplifies this analysis, as it reduces the problem to examining a few specific edge configurations. The method we present is not only applicable across the entire range of traditionally considered parameters n\mathchar 59\relax m\mathchar 59\relax p , but it also provides tight

Read the complete text