Chapter 10 Some Graph Theory and Randomized Algorithms (September 1 1999)

Much of the theory of algorithms deals with algorithms on graphs; conversely, much of the last twenty years of graph theory research pays attention to algorithmic issues. Within these large fields random walks play a comparatively small role, but they do enter in various quite interesting and diverse ways, some of which are described in this chapter. One theme of this chapter is properties of random walks on expander graphs, introduced in sections 10.1.1 and 10.1.2. Some non-probabilistic properties of graphs can be explained naturally (to a probabilist, anyway!) in terms of random walk: see section 10.2. Section 10.3 reviews the general idea of randomized algorithms, and in section 10.4 we treat a diverse sample of randomized algorithms based on random walks. Section 10.5 describes the particular setting of approximate counting, giving details of the case of self-avoiding walks. (xxx details not written in this version).

For simplicity let’s work in the setting of regular graphs. Except where otherwise stated, $G$ is an $n$-vertex $r$-regular connected graph,

is the transition matrix for discrete-time random walk on $G$ (so $P=r^{-1}A$ for the adjacency matrix $A$) and $1=\lambda_{1}>\lambda_{2}\geq\ldots\geq\lambda_{n}\geq-1$ are its eigenvalues, and $\tau_{2}=1/(1-\lambda_{2})$.