Connectivity in discrete random processes

Add to your list(s) Download to your calendar using vCal

• Po-Shen Loh (Carnegie-Mellon)
• Tuesday 07 June 2011, 16:30-17:30
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB.

If you have a question about this talk, please contact Berestycki.

This talk has been canceled/deleted

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.

This talk is part of the Probability series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.