research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleSharp thresholds for Hamiltonicity in random intersection graphs
Bibtex cite IDRACTI-RU1-2010-35
Journal Theoretical Computer Science
Year published 2010
Volume 411
Note to appear
Keywords Random intersection graph; Hamilton cycles; Sharp threshold; Stochastic order relation between Gn,p and Gn,m,p
Random Intersection Graphs, Gn,m,p, is a class of random graphs introduced in Karoński (1999) [7] where each of the n vertices chooses independently a random subset of a universal set of m elements. Each element of the universal sets is chosen independently by some vertex with probability p. Two vertices are joined by an edge iff their chosen element sets intersect. Given n, m so that m=left ceilingnáright ceiling, for any real á different than one, we establish here, for the first time, a sharp threshold for the graph property “Contains a Hamilton cycle”. Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection graph model.
Efthymiou, Charilaos
Spirakis, Paul
Publication ID778