research unit 1
 

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

Publication

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
Abstract
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.
Authors
Efthymiou, Charilaos
Spirakis, Paul
Topics
Top
BibTeXBibTeX
RISRIS
Attachments
 
Publication ID778