# ºtÁ¿¤½§i

### ·s»D¼ÐÃD¡G¡@( 2014-06-19 )

ºtÁ¿¥DÃD¡GGraph coloring games and voter models

¥DÁ¿¤H¡Gª÷ªÚ»T°|¤h ( University of California, San Diego, USA)

ºtÁ¿¤é´Á¡G2014¦~07¤ë10¤é¡]¬P´Á¥|¡^11:10-12:00

ºtÁ¿¦aÂI¡G¤¤¤s¤j¾Ç²z¾Ç°|¥|¼Ó²zSC 4009-1«Ç

ºKn¤º®e¡G

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.