2015/02/02 by Jun Zhao, Zhao, Jun, Osman Yağan +3
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Physics and Society (physics.soc-ph) #Probability (math.PR) #Social and Information Networks (cs.SI) #cs.DM #cs.SI #math.CO #math.PR #physics.soc-ph
paper · pdf · doi:10.48550/arxiv.1502.00395
arxiv created 2015/02/02 · arxiv updated 2015/02/03
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 uniform random s-intersection graph, each vertex independently selects a fixed number of items uniformly at random from a common item pool, while in a binomial random s-intersection graph, each item in some item pool is independently attached to each vertex with the same probability. 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 Conf. on Decision & Control '12]. We show that these threshold functions resemble those of classical Erdős-Rényi graphs, where each pair of vertices has an undirected edge independently with the same probability.