The Social Network model

Speaker  Jonathan Hermon

Affiliation  UC Berkeley

Host  Yuval Peres

Duration  00:53:23

Date recorded  9 January 2013

At time 0 start several independent lazy simple random walks on a finite or infinite connected graph (for instance, start with 1 walker at each vertex). When two walkers visit the same vertex at the same time they are declared acquaintance. The social connectivity time is defined to be the minimal time in which any two walkers have a path of acquaintances between them. The main result in the finite settings (Joint work with Itai Benjamini and Gady Kozma) is poly-logarithmic bounds on the social connectivity time (when the underlying graph is of bounded degree). As time permits a joint work with Ben Morris, Allan Sly and Chuan Qin in which we study the model on infinite graphs will also be discussed. The main question studied: Is it true that a.s. any two walkers will have a path of acquaintances between them? The answer provides a characterization of amenability.

©2013 Microsoft Corporation. All rights reserved.
> The Social Network model