Random s-intersection graphs have recently received considerable attention in a wide range of application areas. In such a graph, each vertex is equipped with a set of items in some random manner, and any two vertices establish an undirected edge in between if and only if they have at least s common items. In particular, in a binomial random s-intersection graph, each item in some item pool is independently attached to each vertex with the same probability, while in a uniform random s-intersection graph, each vertex independently selects a fixed number of items uniformly at random from a common item pool. For binomial/uniform random s-intersection graphs, we establish threshold functions for perfect matching containment, Hamilton cycle containment, and k-robustness, where k-robustness is in the sense of Zhang and Sundaram (IEEE CDC 2012). We show that these threshold functions resemble those of classical Erd??s-R??nyi graphs, in which any two vertices have an undirected edge in between independently with the same probability.
展开▼
