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).
About Fan Chung
After completing her Ph.D. at the University of Pennsylvania in 1974, Fan Chung Graham joined the technical staff of AT&T Bell Laboratories. From 1983 to 1991, she headed the Mathematics, Information Sciences and Operations Research Division at Bellcore, becoming a Bellcore Fellow in 1991. In 1993, she became the Class of 1965 Professor of Mathematics at the University of Pennsylvania. Since 1998, she has been a Professor of Mathematics and Professor of Computer Science and Engineering at the University of California, San Diego and holds the Akamai Chair in Internet Mathematics. Her research interests are primarily in graph theory, combinatorics and algorithm design, in particular in spectral graph theory, extremal graph theory, graph labeling, graph decompositions, random graphs, graph algorithms, parallel structures and various applications of graph theory in Internet computing, communication networks, software reliability, chemistry, engineering and various areas of mathematics.