Connectivity of Random High Dimensional Geometric Graphs

摘要

We consider graphs obtained by placing n points at random on a unit sphere in R~d, and connecting two points by an edge if they are close to each other (e.g., the angle at the origin that their corresponding unit vectors make is at most π /3). We refer to these graphs as geometric graphs. We also consider a complement family of graphs in which two points are connected by an edge if they are far away from each other (e.g., the angle is at least 2π/3). We refer to these graphs as anti-geometric graphs. The families of graphs that we consider come up naturally in the context of semidefinite relaxations of graph optimization problems such as graph coloring. For both distributions, we show that the largest dimension for which a random graph is likely to be connected is the same (up to an additive constant) as the largest dimension for which a random graph is likely not to have isolated vertices. The phenomenon that connectivity of random graphs is tightly related to nonexistence of isolated vertices is not new, and appeared in earlier work both on nongeometric models and on other geometric models. The fact that in our model the dimension d is allowed to grow as a function of n distinguishes our results from earlier results on connectivity of random geometric graphs.