Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 20 min ago
PreprintCC BY 4.0arXiv

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

  • Katarzyna Rybarczyk
  • Grzegorz Serafin
Open at sourcePDFDOICite

Abstract

Let X(r)n denote the number of copies of a complete graph Kr in the random intersection graph model on n vertices. We derive upper bounds on the distance between the standardized version of X(r)n and the standard normal distribution, measured in both the Kolmogorov and Wasserstein metrics. We complement these results with necessary and sufficient conditions for asymptotic normality. As a byproduct, we provide precise estimates for the variance of X(r)n. In the process, we develop new general techniques for analysing so--called clique covers, which play a crucial role in the study of subgraph probabilities in random intersection graphs.

Related

  1. Counting t-wise L-intersecting cliques with prescribed intersection sizes
    Yiyan Zhan, Yichen Wang, Mei Lu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Some advances on stretching operations applied to cliques of edge intersection graphs of paths in trees
    Mariana Escalante, Victoria Kaial, Annegret K Wagler
    HALPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsHAL
  3. Tests of graph homogeneity, subgraph counts, and quasirandomness
    Rudolf Grübel
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  4. Subgraph probabilities in random intersection graphs
    Katarzyna Rybarczyk, Grzegorz Serafin
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Exact Realization of Edge and Induced Three-Vertex Subgraph Counts
    Hillel Schein
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{rybarczyk2026normal,
  title = {{Normal approximation for subgraph counts in random intersection graphs: the case of cliques}},
  author = {Katarzyna Rybarczyk and Grzegorz Serafin},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.27128},
  eprint = {2610.27128},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.27128},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Normal approximation for subgraph counts in random intersection graphs: the case of cliques
AU  - Katarzyna Rybarczyk
AU  - Grzegorz Serafin
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.27128
UR  - https://arxiv.org/abs/2610.27128
AB  - Let X^(r)_n denote the number of copies of a complete graph K_r in the random intersection graph model on n vertices. We derive upper bounds on the distance between the standardized version of X^(r)_n and the standard normal distribution, measured in both the Kolmogorov and Wasserstein metrics. We complement these results with necessary and sufficient conditions for asymptotic normality. As a byproduct, we provide precise estimates for the variance of X^(r)_n. In the process, we develop new general techniques for analysing so--called clique covers, which play a crucial role in the study of subgraph probabilities in random intersection graphs.
ER  -