Poisson approximation of counts of induced subgraphs in random intersection graphs

DOI10.1016/J.DISC.2017.04.013MaRDI QIDQ2359960zbMATH OpenOpenAlexFDO

Authors Katarzyna Rybarczyk, Dudley Stark

Publication date 23 June 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.01699, http://qmro.qmul.ac.uk/xmlui/handle/123456789/17692

zbMATH Keywords

Poisson approximationrandom intersection graphsStein's method

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Random intersection graphs are characterized by three parameters: $n$, $m$ and $p$, where $n$ is the number of vertices, $m$ is the number of objects, and $p$ is the probability that a given object is associated with a given vertex. Two vertices in a random intersection graph are adjacent if and only if they have an associated object in common. When $m=lfloor{n}^{a}lphafloor$ for constant $alpha$, we provide a condition, called {em strictly $alpha$-balanced}, for the Poisson convergence of the number of induced copies of a fixed subgraph.

Recommendations

• Poisson approximation of induced subgraph counts in an inhomogeneous random intersection graph model
• On Random Intersection Graphs: The Subgraph Problem
• Poisson approximation of the number of cliques in random intersection graphs
• The vertex degree distribution of random intersection graphs
• On the isolated vertices and connectivity in random intersection graphs

Cites work

• Equivalence of a random intersection graph and G (n ,p )
• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• On Random Intersection Graphs: The Subgraph Problem
• Poisson approximation of the number of cliques in random intersection graphs
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• Threshold functions for small subgraphs

Cited in

(12)

• The bound on Poisson approximation for the number of induced copies of a fixed graph in a random graph
• Poisson approximation for the number of isolated trees in a random intersection graph
• The bound on Poisson approximation for the number of edges in a random intersection graph on the surface of a sphere
• scientific article; zbMATH DE number 5863938 (Why is no real title available?)
• scientific article; zbMATH DE number 5310725 (Why is no real title available?)
• A Poisson approximation for coloured graphs under exchangeability
• Compound Poisson approximations of subgraph counts in random graphs
• Poisson approximation of the number of cliques in random intersection graphs
• Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges
• Poisson approximation of induced subgraph counts in an inhomogeneous random intersection graph model
• POISSON APPROXIMATION FOR THE NUMBER OF OPIES OF A FIXED GRAPH IN A RANDOM d-REGULAR GRAPH
• The number of triangles in random intersection graphs

This page was built for publication: Poisson approximation of counts of induced subgraphs in random intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2359960)