Speaker Jonathan Hermon
Affiliation UC Berkeley
Host Yuval Peres
Date recorded 9 January 2013
At time 0 start several independent lazy simple random walks on a ﬁnite or inﬁnite 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.
By the same speaker
People also watched
MSR Talk Series: Graph Multi-partitioning and Higher Order Cheeger Inequalities; Anand Louis - Georgia Tech