This website uses features that are not well-supported by your browser. Please consider upgrading to a browser and version that fully supports CSS Grid and the CSS Flexible Box Layout Module.
Sidebar image
NB: A PDF version of this announcement (suitable for posting) is also available.

Connectivity in discrete random processes

Po-Shen Loh
Carnegie Mellon University

Thursday, November 18, 2010
007 Kemeny Hall, 4 pm
Tea 3:30 pm, 300 Kemeny Hall

Abstract: Half a century ago, a seminal paper of Erd\H{o}s and R\'enyi 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 will be accessible to graduate students.