Our treatment of the relaxation time in Chapter 4 emphasized probabilistic interpretations in the broad setting of reversible Markov chains. Specializing to random walk on unweighted graphs, there are a range of non-probabilistic connections between eigenvalues of the adjacency matrix and other graph-theoretic properties. Such spectral graph theory is the subject of Chung [95]: we shall just give a few results with clear probabilistic interpretations.
Implicit in the proof of Theorem 10.1 is that, on a regular graph, the diameter satisfies . By being a little careful we can produce numerical constants.
Proof. The discrete analog of variation threshold satisfies
(10.10) |
because obviously
(10.11) |
Chapter 4 Lemma 26 (yyy 10/11/94 version) specializes to
(10.12) |
We can remove dependence on by the trick of introducing artificial holds. (yyy tie up with Chapter 4 section 3.3). The chain with transition matrix has eigenvalues . Choosing , (this being the value making in the worst case ), we have
Since (10.10) still holds for the Markov chain , combining (10.10) and (10.12) with establishes the Proposition.
Upper bounding via the distinguished paths technique (Chapter 4 section 4.3) (yyy 10/11/94 version) is a valuable theoreticial technique: the essence is to choose paths which “avoid congestion”. In the opposite direction, one can use upper bounds on mixing times to show existence of paths which avoid congestion. Here’s the simplest result of this type. The first part of the proof repeats an idea from Chapter 4 Lemma 21 (yyy new part of Lemma to be added).
Let be any ordering of the vertices of a -regular graph. Then there exists, for each , a path from to such that, writing for the number of times the directed edge is traversed in all the paths,
So on an expander the bound is , using (10.4).
Proof. By definition of , for each vertex there is a segment of the chain such that and has uniform distribution. Take these segments independent as varies. Write for the (random) number of times that is traversed by all these random paths. By considering a uniform random start, by (yyy tie up with Chapter 2 Proposition 3)
In particular, . By erasing loops we may contract each path to a path in which no directed edge is traversed twice. For fixed let be the chance that is traversed by the contracted path from vertex and let be the total number of traversals. By independence of paths as varies,
Choosing makes the bound less that and so
Now repeat the entire construction to define another copy of chain segments with traversal counts . Since and have the same uniform distribution, for each we can construct the chain segments jointly such that . Concatenating paths gives a (non-Markov) random path from to . Then
and so paths with the maximum must exist.
Broder et al. [67] give a more elaborate algorithm for constructing edge-disjoint paths between specified pairs of distinct vertices on an expander, for . The essential idea is to first pick a set of vertices at random, then use a greedy algorithm to construct (as in the proof above) paths from each and to some and in , then for each construct a bundle of random walk paths from to , and finally show that one path may be selected from each bundle so that the set of paths is edge-disjoint.