Nicolas Broutin
Jeudi 28 mars 2013 à 11h, salle 25-26/101
One of the main models for wireless networks is the random geometric graph. In this model, the graph gets connected with high probability only when the average degree is of the order of the logarithm of the size. Although it is not enourmous, it still raises the question of the scalability. Other models (irrigation graphs or Bluetooth graphs) have been devised that sparsify the graph using a local rule and hope that it remains connected. We prove tight threshold for the number of edges necessary for connectivity in this model, showing that the average degree must in particular tend to infinity to expect connectivity. This is joint work with L. Devroye, N. Fraiman and G. Lugosi.