Allerton 2015 Paper Abstract


Paper ThD4.1

Zhao, Jun (CMU & ASU/Princeton)

Threshold Functions in Random s-Intersection Graphs

Scheduled for presentation during the Regular Session "Coding Techniques and Applications II" (ThD4), Thursday, October 1, 2015, 15:30−15:50, Pine

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on December 5, 2021

Keywords Sensor Networks, Social Networks, Sensor Networks in Communications


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. We show that these threshold functions resemble those of classical Erdos-Renyi graphs, where any two vertices have an undirected edge in between independently with the same probability.



All Content © PaperCept, Inc..

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2021 PaperCept, Inc.
Page generated 2021-12-05  08:57:36 PST  Terms of use