Subgraph probabilities in random intersection graphs
Katarzyna Rybarczyk, Grzegorz Serafin
Source 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.