Uniform random intersection graphs have received much interest and been used in diverse applications. A uniform random intersection graph with @math nodes is constructed as follows: each node selects a set of @math different items uniformly at random from the same pool of @math distinct items, and two nodes establish an undirected edge in between if and only if they share at least one item. For such graph denoted by @math , we present the following results in this paper. First, we provide an exact analysis on the probabilities of @math having a perfect matching and having a Hamilton cycle respectively, under @math (all asymptotic notation are understood with @math ). The analysis reveals that just like ( @math -)connectivity shown in prior work, for both properties of perfect matching containment and Hamilton cycle containment, @math also exhibits phase transitions: for each property above, as @math increases, the limit of the probability that @math has the property increases from @math to @math . Second, we compute the phase transition widths of @math for @math -connectivity (KC), perfect matching containment (PMC), and Hamilton cycle containment (HCC), respectively. For a graph property @math and a positive constant @math , with the phase transition width @math defined as the difference between the minimal @math ensuring @math having property @math with probability at least @math or @math , we show for any positive constants @math and @math : (i) If @math and @math , then @math is either @math or @math for each @math sufficiently large. (ii) If @math , then @math . (iii) If @math , then @math . (iv) If @math , @math and @math are both @math .
@cite_13: 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 [email protected]?n^@[email protected]?, for any real @a 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.
@cite_11: Random intersection graphs have received much attention for nearly two decades, and currently have a wide range of applications ranging from key predistribution in wireless sensor networks to modeling social networks. In this paper, we investigate the strengths of connectivity and robustness in a general random intersection graph model. Specifically, we establish sharp asymptotic zero-one laws for k-connectivity and k-robustness, as well as the asymptotically exact probability of k-connectivity, for any positive integer k. The k-connectivity property quantifies how resilient is the connectivity of a graph against node or edge failures. On the other hand, k-robustness measures the effectiveness of local diffusion strategies (that do not use global graph topology information) in spreading information over the graph in the presence of misbehaving nodes. In addition to presenting the results under the general random intersection graph model, we consider two special cases of the general model, a binomial random intersection graph and a uniform random intersection graph, which both have numerous applications as well. For these two specialized graphs, our results on asymptotically exact probabilities of k-connectivity and asymptotic zero-one laws for k-robustness are also novel in the literature.
@cite_2: We present new results concerning threshold functions for a wide family of random intersection graphs. To this end we apply the coupling method used for establishing threshold functions for homogeneous random intersection graphs introduced by Karo 'nski, Scheinerman, and Singer--Cohen. In the case of inhomogeneous random intersection graphs the method has to be considerably modified and extended. By means of the altered method we are able to establish threshold functions for a general random intersection graph for such properties as @math -connectivity, matching containment or hamiltonicity. Moreover using the new approach we manage to sharpen the best known results concerning homogeneous random intersection graph.
@cite_17: 
A graph model related to uniform random intersection graphs is the so-called : each item in a pool is assigned to each node independently with the same probability, and two nodes establish an undirected edge upon sharing at least one item. Note that here the number of items on each node follows a binomial distribution. This graph model has also been studied in the literature as noted below. For connectivity, Rybarczyk presents a zero--one law @cite_17 and later obtains the stronger result of the asymptotically exact probability @cite_2 . For @math -connectivity, she establishes zero--one laws @cite_17 @cite_2 , and we compute the asymptotically exact probability @cite_11 . For perfect matching containment, Rybarczyk provides a zero--one law @cite_17 and derives the asymptotically exact probability @cite_2 . For Hamilton cycle containment, Efthymioua and Spirakis @cite_13 , and Rybarczyk @cite_17 @cite_2 show zero--one laws.