Colloquium / Seminars
Topic:Graph coloring games and voter models
Speaker:Fan Chung Graham
( University of California, San Diego, USA)Date time:July 10, 2014 11:10-12:00
Venue:SC Room 4009-1, Department of Applied Mathematics,
Abstract:
We investigate certain random processes on graphs which are related to the so-called Tsetlin library random walks as well as to some variants of classical voter model. A specific example can be described as a hypergraph coloring game. Each node represents a voter and is colored according to its preferred candidate, or undecided. Each hyperedge is a subset of nodes and can be viewed as a chat group. In each round of the game, one chat group is chosen randomly, and voters in the group can change colors based on interactions. We analyze the game as a random walk on the associated weighted directed state graph. Under certain `memoryless' conditions, the spectrum of the state graph can be explicitly determined by using semigroup spectral theory. It can be shown that random walk on the state graph converges to its stationary distribution in $O(m \log n)$ time, where $n$ denotes the number of voters and $m$ denotes the number of chat groups. This can then be used to determine the appropriate cut-off time for voting. We also consider a partial memoryless version which can be used to approximate general voter games.
This is based on joint papers with Ron Graham and Alex Tsiatas.
go back