The coupling method for inhomogeneous random intersection graphs.

zbMATH Open1361.05118arXiv1301.0466MaRDI QIDQ528984FDOQ528984

Katarzyna Rybarczyk

Publication date: 18 May 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We present new results concerning threshold functions for a wide family of random intersection graphs. To this end we apply the coupling method used for establishing threshold functions for homogeneous random intersection graphs introduced by Karo'nski, Scheinerman, and Singer--Cohen. In the case of inhomogeneous random intersection graphs the method has to be considerably modified and extended. By means of the altered method we are able to establish threshold functions for a general random intersection graph for such properties as $k$-connectivity, matching containment or hamiltonicity. Moreover using the new approach we manage to sharpen the best known results concerning homogeneous random intersection graph.

Full work available at URL: https://arxiv.org/abs/1301.0466

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Publication:4729111
• Degree distribution of an inhomogeneous random intersection graph
• The degree distribution in random intersection graphs
• On Connectivity and Robustness in Random Intersection Graphs
• On Connectivity in a General Random Intersection Graph
• Sharp threshold functions for random intersection graphs via a coupling method
• Connectivity of inhomogeneous random graphs
• RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING
• The vertex degree distribution of random intersection graphs
• A guided tour in random intersection graphs

zbMATH Keywords

threshold functionrandom intersection graphmonotone property

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Connectivity (05C40)

Cites Work

• Perfect matchings in random intersection graphs
• Title not available (Why is that?)
• On Random Intersection Graphs: The Subgraph Problem
• Equivalence of a random intersection graph and G (n ,p )
• Title not available (Why is that?)
• 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
• Component evolution in a secure wireless sensor network
• Large independent sets in general random intersection graphs
• Component Evolution in General Random Intersection Graphs
• Degree and clustering coefficient in sparse random intersection graphs
• The shortest distance in random multi-type intersection graphs
• Epidemics on Random Graphs with Tunable Clustering
• RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING
• Degree distribution of an inhomogeneous random intersection graph
• Sharp threshold functions for random intersection graphs via a coupling method

Cited In (4)

• Title not available (Why is that?)
• A Note on the Conductance of the Binomial Random Intersection Graph
• Hamilton cycles in the line graph of a random hypergraph
• Title not available (Why is that?)

This page was built for publication: The coupling method for inhomogeneous random intersection graphs.

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