printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

food for thought seminar

jacob hughes

ucsd

random lights out processes on graphs

abstract:

lights out is a single player game on graph g. the game starts with a coloring of the vertices of g with two colors, 0 and 1. at each step, one vertex is toggled which switches the color of that vertex and all of its neighbors. the game is won when all vertices have color 0. this game can be analyzed using linear algebra over a finite field, for example the number of solvable colorings of a graph is 2 to the rank of a + i, where a is the adjacency matrix of the graph, and i is the identity. we consider the stochastic process arising from toggling a sequence of random vertices. we demonstrate how the process can be viewed as a random walk on an associated state graph. we then find the eigenvalues of the state graph, and use them to bound the rate of convergence and hitting times. we also provide bounds on the average number of steps until this random process reaches the all 0 coloring that are asymptotically tight for many families of graphs.

host: michael kasa

november 15, 2012

10:00 am

ap&m 7321

****************************