Allerton 2015 Paper Abstract

Close

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 November 19, 2019

Keywords Sensor Networks, Social Networks, Sensor Networks in Communications

Abstract

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-2019 PaperCept, Inc.
Page generated 2019-11-19  13:06:19 PST  Terms of use