Efthymiou, Charilaos and Spirakis, Paul G.. (2010) Sharp thresholds for Hamiltonicity in random intersection graphs. Theoretical Computer Science, Vol.411 (No.40-42). pp. 3714-3730. ISSN 0304-3975

Full text not available from this repository.

Abstract

Random Intersection Graphs, G(n,m,p), is a class of random graphs introduced in Karonski (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 = inverted right perpendicularn(alpha)inverted left perpendicular, for any real alpha 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. (C) 2010 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	Theoretical Computer Science
Publisher:	Elsevier Science BV
ISSN:	0304-3975
Date:	6 September 2010
Volume:	Vol.411
Number:	No.40-42
Number of Pages:	17
Page Range:	pp. 3714-3730
Identification Number:	10.1016/j.tcs.2010.06.022
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Version or Related Resource:	A preliminary version of this work was presented at ICALP 2005, Efthymiou and Spirakis (2005)
URI:	http://wrap.warwick.ac.uk/id/eprint/5050

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item