Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, March 10, 2015 - 2:30pm

Omer Tamuz

MIT

Location

University of Pennsylvania

DRL 4E9

A group of people connected by a social network each start with some opinion in {0,1}. They then proceed to repeatedly update their opinions by conforming to those of the majority of their neighbors. On finite graphs, this model has the curious property that, when updates are synchronous, each person eventually either converges to a fixed opinion or else, from some point on, oscillates between the two possible opinions with period two. When updates are asynchronous each person's opinion converges. We will study this model on infinite graphs and random graphs, showing some old results, some new ones, and some nice open questions. Joint work with Ran Tessler.