Tutte 100th Colloquium - Fan Chung Graham

Title: Semigroup spectral methods and graph coloring games 

Abstract:

We consider a coloring game on graphs as an example to illustrate the effectiveness of the semigroup spectral method for determining the spectrum of the directed graphs which arise as the state graphs associated with the game. Originating from the study of the so-called Tsetlin library random walks and the like, this  method can be used to  analyze dynamic processes such as  voting and ranking, provided the random processes satisfy certain "memoryless" conditions (corresponding to left-regular-band semigroups).