Rutgers Discrete Mathematics Seminar

Title: Connectivity of Geometric k-out Graphs

Speaker: Nicolas Fraiman, University of Pennsylvania

Date: Tuesday, March 4, 2014 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ


Consider n uniform random points in the unit square. One may form a random geometric graph by connecting two points by an edge if their distance is at most r. For a positive integer k, we form a subgraph of the random geometric graph by selecting, at random, k vertices among the neighbors of any given vertex, and keeping only the edges joining the vertex to the selected neighbors. We present results about connectivity properties of such graphs.

This is joint work with Nicolas Broutin, Luc Devroye and Gabor Lugosi.