CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Math Colloquium
Po-Shen Loh
Princeton
Title: Random graphs, and the power of two choices

Abstract: Since their introduction half a century ago, probabilistic methods have elegantly provided a wide variety of otherwise difficult to find constructions. Combinatorial applications often employ variants of the Erd?s-Rényi random graph Gn,p, an n-vertex graph obtained by independently placing an edge between each vertex pair with probability p. In addition to being useful for constructions, these objects are interesting in their own right. One beautiful discovery was that many important graph properties appear suddenly: when p crosses a certain threshold, the probability that Gn,p satisfies the property jumps from nearly 0 to nearly 1. Another remarkable probabilistic phenomenon, of separate origin, is known as the "power of two random choices". When n balls are distributed into n bins by sequentially sending each ball into an independent random bin, then the fullest bin typically contains log n ? log log n balls. However, if each ball instead receives two independent random choices of a target bin, and selects the lesser-occupied one, then the maximum occupancy falls dramatically. In this talk, I will survey the above, and discuss progress (including joint work with M. Krivelevich and B. Sudakov) in a newer model which unites both of the above phenomena. Recent research suggests that the two-choices paradigm also holds in the graph setting, as various authors have shown that thresholds for several classical graph properties can indeed be substantially affected by this power.

Date: Tuesday, February 24, 2009
Time: 4:30 pm
Location: Doherty Hall A310