The Social Network model

Опубликовано 27 июля 2016, 0:35

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.