Connectivity in discrete random processes

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

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

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

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:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB
• Probability
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.