Random Seidel Switching on Graphs

Abstract

We consider the random process arising from a sequence of random Seidel switching operations on $n$ vertices. We show that this process can be interpreted as a random walk on a Cayley graph of an abelian group, and use spectral methods to show that the random process converges to a stationary distribution in $O(n\log (n))$ steps. We then consider two generalizations: we allow multiple states for each edge, and restrict the process to a fixed host graph $H$. We then analyze the general case and obtain convergence results for any graph $H$.