Sharp thresholds for Hamiltonicity in random intersection graphs
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-3975Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.tcs.2010.06.022
Random Intersection Graphs, G(n,m,p), is a class of random graphs introduced in Karonski (1999)  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|
|Official Date:||6 September 2010|
|Number of Pages:||17|
|Page Range:||pp. 3714-3730|
|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)|
Actions (login required)
Downloads per month over past year