UC San Diego

In this thesis, we study a collection of stochastic properties arising from graph manipulations. These manipulations may change the structure of the graph itself, recolor the vertices, or alter other assigned properties. Our goal with each process is to use a combination of combinatorial, spectral, and algebraic methods to analyze the stationary distribution, mixing times, and hitting times of these stochastic processes. In particular, we do the following : We consider the random process on a class of semigroup known Left Regular Bands induced my multiplying by randomly selected generators. Such a process converges to a stationary distribution, and we present a bound the convergence time which slightly improves previous results. We consider the random process induced by random Seidel switching on a graph, an operation that transforms a graph by inverting the adjacency relations at a vertex. By computing the spectrum of the state graph of this process we show the process converges and bound the mixing time. We also consider several generalizations of Seidel switching. We study a stochastic process arising from randomly playing the Lights Out game on an arbitrary nite graph. In this game, the vertices are colored black or white, and a toggle changes state of that vertex and all of its neighbors. We obtain a bounds on the mixing time and average hitting time of the all black coloring. We investigate the random process on phylogenetic trees induced by nearest neighbor interchanges, an operation that swaps two neighboring sub- trees. We use a comparison theorem to bound the spectral gap of the state graph and use this to bound the mixing time of the random nearest neighbor interchange process. We introduce the multi-commodity dynamic demand model on a graph, a variant of the standard contact process on graphs. Each vertex has a list of demands for various commodities, and the demands of a vertex influence the demands of its neighbors. We introduce a generalization of the PageRank vector, Kronecker PageRank, and use it to bound the amount of commodities needed to satisfy the demand at the vertices