Random Intersection Graphs is a new class of random graphs introduced in [5], in which each of n vertices randomly and independently chooses some elements from a universal set, of cardinality m. Each element is chosen 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 a different than one, we establish here, for the first time, tight lower bounds p_0(n, m), on the value of p, as a function of n and m, above which the graph G_(n,m,p) is almost certainly Hamiltonian, i.e. it contains a Hamilton Cycle almost certainly. Our bounds are tight in the sense that when p is asymptotically smaller than p_0(n, m) then G_(n,m,p) almost surely has a vertex of degree less than 2. Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection model. Interestingly, Hamiltonicity appears well below the general thresholds, of [4], at which G_(n,m,p) looks like a usual random graph. Thus our bounds are much stronger than the trivial bounds implied by those thresholds. Our results strongly support the existence of a threshold for Hamiltonicity in G_(n,m,p).
展开▼
