Normal approximation for number of edges in random intersection graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909557697019904 |
|---|---|
| author | Rybarczyk, Katarzyna Serafin, Grzegorz |
| author_facet | Rybarczyk, Katarzyna Serafin, Grzegorz |
| contents | The random intersection graph model $\mathcal G(n,m,p)$ is considered. Due to substantial edge dependencies, studying even fundamental statistics such as the subgraph count is significantly more challenging than in the classical binomial model $\mathcal G(n,p)$. First, we establish normal approximation bound in both the Wasserstein and the Kolmogorov distances for a class of local statistics on $\mathcal G(n,m,p)$. Next, we apply these results to derive such bounds for the standardised number of edges, and determine the necessary and sufficient conditions for its asymptotic normality. We develop a new method that provides a combinatorial interpretation and facilitates the estimation of analytical expressions related to general distance bounds. In particular, this allows us to control the behaviour of central moments of subgraph existence indicators. The presented method can also be extended to count copies of subgraphs larger than a single edge. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23110 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Normal approximation for number of edges in random intersection graphs Rybarczyk, Katarzyna Serafin, Grzegorz Combinatorics Probability 05C80, 60F05, 05C82 The random intersection graph model $\mathcal G(n,m,p)$ is considered. Due to substantial edge dependencies, studying even fundamental statistics such as the subgraph count is significantly more challenging than in the classical binomial model $\mathcal G(n,p)$. First, we establish normal approximation bound in both the Wasserstein and the Kolmogorov distances for a class of local statistics on $\mathcal G(n,m,p)$. Next, we apply these results to derive such bounds for the standardised number of edges, and determine the necessary and sufficient conditions for its asymptotic normality. We develop a new method that provides a combinatorial interpretation and facilitates the estimation of analytical expressions related to general distance bounds. In particular, this allows us to control the behaviour of central moments of subgraph existence indicators. The presented method can also be extended to count copies of subgraphs larger than a single edge. |
| title | Normal approximation for number of edges in random intersection graphs |
| topic | Combinatorics Probability 05C80, 60F05, 05C82 |
| url | https://arxiv.org/abs/2503.23110 |