Sharp threshold functions for random intersection graphs via a coupling method

MaRDI QIDQ625409zbMATH OpenFDO

Authors Katarzyna Rybarczyk

Publication date 17 February 2011

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

Full work available at URL https://arxiv.org/abs/0910.0749, https://eudml.org/doc/229176, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p36.html

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

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)

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.

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

Cited in

(9)

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