Our treatment of the relaxation time $\tau_{2}$ 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 $\Delta$ satisfies $\Delta=O(\tau)=O(\tau_{2}\log n)$. By being a little careful we can produce numerical constants.

$\Delta/2\leq\left\lceil\frac{1+{\textstyle\frac{1}{2}}\log n}{\log{\textstyle% \frac{3-\lambda_{2}}{1+\lambda_{2}}}}\right\rceil.$

Proof. The discrete analog $\tau_{1}^{{\rm disc}}$ of variation threshold satisfies

$\tau_{1}^{{\rm disc}}\geq\Delta/2,$ | (10.10) |

because obviously

$\mbox{ if }d(v,w)=\Delta\mbox{ and }t<\Delta/2\mbox{ then }||P_{v}(X_{t}\in% \cdot)-P_{w}(X_{t}\in\cdot)||=1.$ | (10.11) |

Chapter 4 Lemma 26 (yyy 10/11/94 version) specializes to

$\tau_{1}^{{\rm disc}}\leq\left\lceil\frac{1+{\textstyle\frac{1}{2}}\log n}{% \log 1/\beta}\right\rceil,\quad\beta:=\max(\lambda_{2},-\lambda_{n}).$ | (10.12) |

We can remove dependence on $\lambda_{n}$ by the trick of introducing artificial holds. (yyy tie up with Chapter 4 section 3.3). The chain with transition matrix $P^{\prime}:=\theta I+(1-\theta)P$ has eigenvalues $\lambda_{i}^{\prime}=\theta+(1-\theta)\lambda_{i}$. Choosing $\theta=(1-\lambda_{2})/(3-\lambda_{2})$, (this being the value making $\lambda_{2}^{\prime}=-\lambda_{n}^{\prime}$ in the worst case $\theta_{n}=-1$), we have

${\textstyle\frac{1+\lambda_{2}}{3-\lambda_{2}}}=\beta^{\prime}=\lambda_{2}^{% \prime}\geq-\lambda_{n}^{\prime}.$ |

Since (10.10) still holds for the Markov chain $P^{\prime}$, combining (10.10) and (10.12) with $\beta^{\prime}$ establishes the Proposition.

Upper bounding $\tau_{2}$ 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 $v(1),v(2),\ldots,v(n)$ be any ordering of the vertices $1,2,\ldots,n$ of a $r$-regular graph. Then there exists, for each $1\leq i\leq n$, a path from $i$ to $v(i)$ such that, writing $N_{vw}$ for the number of times the directed edge $(v,w)$ is traversed in all the paths,

$\max_{(v,w)}N_{vw}\leq 7\max\left(e\tau_{1}^{(2)}/r,\log n\right).$ |

So on an expander the bound is $O(\log n)$, using (10.4).

Proof. By definition of $\tau_{1}^{(2)}$, for each vertex $i$ there is a segment of the chain $i=X^{(i)}_{0},X^{(i)}_{1},\ldots,X^{(i)}_{U_{i}}$ such that $EU_{i}\leq\tau^{(2)}_{1}$ and $X^{(i)}_{U_{i}}$ has uniform distribution. Take these segments independent as $i$ varies. Write $\tilde{N}_{vw}$ for the (random) number of times that $(v,w)$ is traversed by all these random paths. By considering a uniform random start, by (yyy tie up with Chapter 2 Proposition 3)

${\textstyle\frac{1}{n}}E\tilde{N}_{vw}={\textstyle\frac{1}{rn}}\ \sum_{i}{% \textstyle\frac{1}{n}}EU_{i}.$ |

In particular, $E\tilde{N}_{vw}\leq\tau^{(2)}_{1}/r:=\kappa$. By erasing loops we may contract each path to a path in which no directed edge is traversed twice. For fixed $(v,w)$ let $p_{i}$ be the chance that $(v,w)$ is traversed by the contracted path from vertex $i$ and let $N^{\prime}_{vw}$ be the total number of traversals. By independence of paths as $i$ varies,

$\displaystyle P(N^{\prime}_{vw}\geq m)$ | $\displaystyle\leq$ | $\displaystyle\left(\sum_{i}p_{i}\right)^{m}/m!\quad\mbox{ (expand the sum)}$ | ||

$\displaystyle\leq$ | $\displaystyle\kappa^{m}/m!\leq(e\kappa/m)^{m}.$ |

Choosing $m=\lceil 3\max(e\kappa,\log n)\rceil$ makes the bound less that $1/(2n^{2})$ and so

$P\left(\max_{(v,w)}N^{\prime}_{vw}\geq m\right)<1/2.$ |

Now repeat the entire construction to define another copy $(Y^{(i)}_{t},0\leq t\leq V_{i})$ of chain segments with traversal counts $N^{\prime\prime}_{vw}$. Since $X^{(i)}_{U_{i}}$ and $Y^{(v(i))}_{V_{i}}$ have the same uniform distribution, for each $i$ we can construct the chain segments jointly such that $X^{(i)}_{U_{i}}=Y^{(v(i))}_{V_{i}}$. Concatenating paths gives a (non-Markov) random path from $i$ to $v(i)$. Then

$P\left(\max_{(v,w)}N^{\prime}_{vw}+N^{\prime\prime}_{vw}\geq 2m\right)<1$ |

and so paths with the maximum $\leq 2m-1$ must exist.

Broder et al. [67] give a more elaborate algorithm for constructing edge-disjoint paths between specified pairs $\{(a_{i},b_{i}),1\leq i\leq k\})$ of distinct vertices on an expander, for $k=n^{1-o(1)}$. The essential idea is to first pick a set $S$ of $4k$ vertices at random, then use a greedy algorithm to construct (as in the proof above) paths from each $a_{i}$ and $b_{i}$ to some $\tilde{a}_{i}$ and $\tilde{b}_{i}$ in $S$, then for each $i$ construct a bundle of random walk paths from $\tilde{a}_{i}$ to $\tilde{b}_{i}$, and finally show that one path may be selected from each bundle so that the set of paths is edge-disjoint.

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML