Sharp threshold functions for random intersection graphs via a coupling method

zbMATH Open1229.05250arXiv0910.0749MaRDI QIDQ625409FDOQ625409

Authors: Katarzyna Rybarczyk 

Publication date: 17 February 2011

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

Abstract: We will present a new method, which enables us to find threshold functions for many properties in random intersection graphs. This method will be used to establish sharp threshold functions in random intersection graphs for k-connectivity, perfect matching containment and Hamilton cycle containment.

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

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

Recommendations

• Sharp threshold functions via a coupling method
• The coupling method for inhomogeneous random intersection graphs.
• Sharp thresholds for Hamiltonicity in random intersection graphs
• Equivalence of a random intersection graph and G (n ,p )
• Automata, Languages and Programming

zbMATH Keywords

couplingconnectivityHamilton cycleperfect matchingrandom intersection graphsthreshold functions

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (9)

• Asymptotic distribution of isolated nodes in secure wireless sensor networks under transmission constraints
• Recent advances on the Hamiltonian problem: survey III
• On the complexity of the herding attack and some related attacks on hash functions
• Perfect matchings in random intersection graphs
• Phase transitions for detecting latent geometry in random graphs
• Size of the largest component in a critical graph
• The largest component in critical random intersection graphs
• Sharp thresholds for Hamiltonicity in random intersection graphs
• The coupling method for inhomogeneous random intersection graphs.

This page was built for publication: Sharp threshold functions for random intersection graphs via a coupling method

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