Abstract

Half a century ago, a seminal paper of Erdos and Renyi launched the systematic study of random graphs. Since then, this direction of investigation has blossomed into a broad field, and the original model has given rise to many useful variants. Of the properties which have received attention, one of the most fundamental has been that of global connectivity.

Recently, motivated by the practical problem of establishing connectivity in peer-to-peer networks, a natural question of similar flavor arose in the analysis of a natural randomized clustering algorithm. Using methods which originated from physics, but now known to be remarkably useful in the study of random graphs, we establish the asymptotic optimality of this algorithm. We also prove the first rigorous lower bounds on the performance of a closely-related algorithm, extending an approach of Oded Schramm.

Joint work with Eyal Lubetzky.