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

Subgraph probabilities in random intersection graphs

  • Katarzyna Rybarczyk
  • Grzegorz Serafin
Open at sourcePDFDOICite

Abstract

Since their introduction by Karoński, Scheinerman, and Singer-Cohen in 90's, random intersection graphs have attracted much attention, mostly due to their various applications. In this article, we establish a general result for the probability that a given small subgraph is present in a random intersection graph. Our theorem applies to a broad range of parameters, including regimes that have not previously been considered in the literature. Moreover, it extends known results and situates them within a broader framework, making this approach a convenient tool for comparing the probabilities of graphs in the random intersection graph model. To prove our main result, we develop new proof techniques that, to the best of our knowledge, have not previously been employed in the study of small subgraphs in random intersection graphs. Many special cases and examples are presented as well.

Related

  1. Normal approximation for subgraph counts in random intersection graphs: the case of cliques
    Katarzyna Rybarczyk, Grzegorz Serafin
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Fluctuations of subgraph counts in exponential random graphs
    Hui-Lin Liu, Song-Hao Liu, Dawei Lu
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  3. Upper tail large deviations of regular subgraph counts in sparse random regular graphs
    Anirban Basak, Shaibal Karmakar
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Last-Coverage Probabilities of Random Walks on Cycle Graphs for Symmetric, Biased, and Time-Dependent Walks
    Kiyan Idnani, Jad Salem
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  5. Orthogonality graphs of real Cayley-Dickson algebras. Part II: The subgraph on pairs of basis elements
    Svetlana Zhilina
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{rybarczyk2026subgraph,
  title = {{Subgraph probabilities in random intersection graphs}},
  author = {Katarzyna Rybarczyk and Grzegorz Serafin},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.27117},
  eprint = {2610.27117},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.27117},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Subgraph probabilities in random intersection graphs
AU  - Katarzyna Rybarczyk
AU  - Grzegorz Serafin
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.27117
UR  - https://arxiv.org/abs/2610.27117
AB  - Since their introduction by Karoński, Scheinerman, and Singer-Cohen in 90's, random intersection graphs have attracted much attention, mostly due to their various applications. In this article, we establish a general result for the probability that a given small subgraph is present in a random intersection graph. Our theorem applies to a broad range of parameters, including regimes that have not previously been considered in the literature. Moreover, it extends known results and situates them within a broader framework, making this approach a convenient tool for comparing the probabilities of graphs in the random intersection graph model. To prove our main result, we develop new proof techniques that, to the best of our knowledge, have not previously been employed in the study of small subgraphs in random intersection graphs. Many special cases and examples are presented as well.
ER  -