Sharp thresholds for Hamiltonicity in random intersection graphs

AbstractRandom 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=⌈nα⌉, 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