10.2 Eigenvalues and graph theory

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.

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

because obviously

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

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

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).

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)

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,

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

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

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.