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

10.2 Eigenvalues and graph theory

Our treatment of the relaxation time τ2\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.

10.2.1 Diameter of a graph

Implicit in the proof of Theorem 10.1 is that, on a regular graph, the diameter Δ\Delta satisfies Δ=O(τ)=O(τ2logn)\Delta=O(\tau)=O(\tau_{2}\log n). By being a little careful we can produce numerical constants.

Proposition 10.4

Δ/21+12lognlog3-λ21+λ2.\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 τ1disc\tau_{1}^{{\rm disc}} of variation threshold satisfies

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

because obviously

 if d(v,w)=Δ and t<Δ/2 then ||Pv(Xt)-Pw(Xt)||=1.\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

τ1disc1+12lognlog1/β, β:=max(λ2,-λn).\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 λn\lambda_{n} by the trick of introducing artificial holds. (yyy tie up with Chapter 4 section 3.3). The chain with transition matrix P:=θI+(1-θ)PP^{\prime}:=\theta I+(1-\theta)P has eigenvalues λi=θ+(1-θ)λi\lambda_{i}^{\prime}=\theta+(1-\theta)\lambda_{i}. Choosing θ=(1-λ2)/(3-λ2)\theta=(1-\lambda_{2})/(3-\lambda_{2}), (this being the value making λ2=-λn\lambda_{2}^{\prime}=-\lambda_{n}^{\prime} in the worst case θn=-1\theta_{n}=-1), we have

1+λ23-λ2=β=λ2-λn.{\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 PP^{\prime}, combining (10.10) and (10.12) with β\beta^{\prime} establishes the Proposition.

10.2.2 Paths avoiding congestion

Upper bounding τ2\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).

Proposition 10.5

Let v(1),v(2),,v(n)v(1),v(2),\ldots,v(n) be any ordering of the vertices 1,2,,n1,2,\ldots,n of a rr-regular graph. Then there exists, for each 1in1\leq i\leq n, a path from ii to v(i)v(i) such that, writing NvwN_{vw} for the number of times the directed edge (v,w)(v,w) is traversed in all the paths,

max(v,w)Nvw7max(eτ1(2)/r,logn).\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(logn)O(\log n), using (10.4).

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

1nEN~vw=1rni1nEUi.{\textstyle\frac{1}{n}}E\tilde{N}_{vw}={\textstyle\frac{1}{rn}}\ \sum_{i}{% \textstyle\frac{1}{n}}EU_{i}.

In particular, EN~vwτ1(2)/r:=κ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)(v,w) let pip_{i} be the chance that (v,w)(v,w) is traversed by the contracted path from vertex ii and let NvwN^{\prime}_{vw} be the total number of traversals. By independence of paths as ii varies,

P(Nvwm)\displaystyle P(N^{\prime}_{vw}\geq m) \displaystyle\leq (ipi)m/m! (expand the sum)\displaystyle\left(\sum_{i}p_{i}\right)^{m}/m!\quad\mbox{ (expand the sum)}
\displaystyle\leq κm/m!(eκ/m)m.\displaystyle\kappa^{m}/m!\leq(e\kappa/m)^{m}.

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

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

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

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

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

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