6 Cover Times (October 31, 1994)

6.1 The spanning tree argument

Except for Theorem 6.1, we consider in this section random walk on an nn-vertex unweighted graph. Results can be stated in terms of the number of edges |||\mbox{${\cal E}$}| of the graph, but to aid comparison with results involving minimal or maximal degree it is helpful to state results in terms of average degree d¯\bar{d}:

d¯=2||n;   ||=nd¯/2.\bar{d}=\frac{2|\mbox{${\cal E}$}|}{n};\ \ \ \ \ \ |\mbox{${\cal E}$}|=n\bar{d% }/2.

The argument for Theorem 6.1 goes back to Aleliunas et al [25]. Though elementary, it can be considered the first (both historically and logically) result which combines Markov chain theory with graph theory in a non-trivial way.

Consider random walk on a weighted graph. Recall from Chapter 3 yyy the edge-commute inequality: for an edge (v,x)(v,x)

EvTx+ExTv\displaystyle E_{v}T_{x}+E_{x}T_{v} \displaystyle\leq w/wvx   (weighted)\displaystyle w/w_{vx}\ \ \ \ \mbox{ (weighted) } (6.1)
\displaystyle\leq d¯n     (unweighted).\displaystyle\bar{d}n\ \ \ \ \ \mbox{ (unweighted). } (6.2)

One can alternatively derive these inequalities from the commute interpretation of resistance (Chapter 3 yyy), since the resistance between xx and vv is at most 1/wvx1/w_{vx}.

Theorem 6.1

For random walk on a weighted graph,

maxvEvC+wmin𝒯e𝒯1/we\max_{v}E_{v}C^{+}\leq w\min_{\mbox{${\cal T}$}}\sum_{e\in\mbox{${\cal T}$}}1/% w_{e}

where the min is over spanning trees 𝒯{\cal T}. In the unweighted case


Proof. Given a spanning tree 𝒯{\cal T} and a vertex vv, there is a path v=v0,v1,,v2n-2=vv=v_{0},v_{1},\ldots,v_{2n-2}=v which traverses each edge of the tree once in each direction, and in particular visits every vertex. So

EvC+\displaystyle E_{v}C^{+} \displaystyle\leq j=02n-3EvjTvj+1\displaystyle\sum_{j=0}^{2n-3}E_{v_{j}}T_{v_{j+1}}
=\displaystyle= e=(v,x)𝒯(EvTx+ExTv)\displaystyle\sum_{e=(v,x)\in\mbox{${\cal T}$}}(E_{v}T_{x}+E_{x}T_{v})
\displaystyle\leq e𝒯w/we by (6.1)\displaystyle\sum_{e\in\mbox{${\cal T}$}}w/w_{e}\mbox{ by }(\ref{cominew})

This gives the weighted case, and in the unweighted case w=d¯nw=\bar{d}n and each spanning tree has e𝒯1/we=n-1\sum_{e\in\mbox{${\cal T}$}}1/w_{e}=n-1. \Box

Note that in the unweighted case, the bound is at most n(n-1)2n(n-1)^{2}. On the barbell (Chapter 5 Example yyy) it is easy to see that miniEiC=Ω(n3)\min_{i}E_{i}C=\Omega(n^{3}), so the maximal values of any formalization of “mean cover time”, over nn-vertex graphs, is Θ(n3)\Theta(n^{3}). Results and conjectures on the optimal numerical constants in the Θ(n3)\Theta(n^{3}) upper bounds are given in section 6.3.

Corollary 6.2

On an unweighted nn-vertex tree, EvCv+2(n-1)2E_{v}C^{+}_{v}\leq 2(n-1)^{2}, with equality iff the tree is the nn-path and vv is a leaf.

Proof. The inequality follows from Theorem 6.1. On the nn-path with leaves v,zv,z we have EvCv+=EvTz+EzTv=2(n-1)2E_{v}C^{+}_{v}=E_{v}T_{z}+E_{z}T_{v}=2(n-1)^{2}. \Box

It is worth dissecting the proof of Theorem 6.1. Two different inequalities are used in the proof. Inequality (6.2) is an equality iff the edge is essential, so the second inequality in the proof is an equality iff the graph is a tree. But the first inequality in the proof bounds C+C^{+} by the time to traverse a spanning tree in a particular order, and is certainly not sharp on a general tree, but only on a path. This explains Corollary 6.2. More importantly, these remarks suggest that the bound d¯n(n-1)\bar{d}n(n-1) in Theorem 6.1 will be good iff there is some fixed “essential path” in the graph, and the dominant contribution to CC is from the time taken to traverse that path (as happens on the barbell).

There are a number of variations on the theme of Theorem 6.1, and we will give two. The first (due to Zuckerman [342], whose proof we follow) provides a nice illustration of probabilistic technique.

Proposition 6.3

Write CeC_{e} for the time to cover all edges of an unweighted graph, i.e. until each edge (v,w)(v,w) has been traversed in each direction. Then

maxvEvCe11d¯n2.\max_{v}E_{v}C_{e}\leq 11\bar{d}n^{2}.

Proof. Fix a vertex vv and a time t0t_{0}. Define “excursions”, starting and ending at vv, as follows. In each excursion, wait until all vertices have been visited, then wait t0t_{0} longer, then end the excursion at the next visit to vv. Writing SiS_{i} for the time at which the ii’th excursion ends, and NN for the (random) number of excursions required to cover each edge in each direction, we have

SN=min{Si:SiCe}S_{N}=\min\{S_{i}:S_{i}\geq C_{e}\}

and so by Wald’s identity (yyy refs)

EvCeEvSN=EvN×EvS1.E_{v}C_{e}\leq E_{v}S_{N}=E_{v}N\times E_{v}S_{1}. (6.3)


EvS1EvC+t0+maxwEwTvt0+2maxiEiC.E_{v}S_{1}\leq E_{v}C+t_{0}+\max_{w}E_{w}T_{v}\leq t_{0}+2\max_{i}E_{i}C.

To estimate the other factor, we shall first show

Pv(N>2)m3/t02P_{v}(N>2)\leq m^{3}/t^{2}_{0} (6.4)

where md¯nm\equiv\bar{d}n is the number of directed edges. Fix a directed edge (w,x)(w,x), say. By Chapter 3 Lemma yyy the mean time, starting at xx, until (w,x)(w,x) is traversed equals mm. So the chance, starting at xx, that (w,x)(w,x) is not traversed before time t0t_{0} is at most m/t0m/t_{0}. So using the definition of excursion, the chance that (v,w)(v,w) is not traversed during the first excursion is at most m/t0m/t_{0}, so the chance it is not traversed during the first two excursions is at most (m/t0)2(m/t_{0})^{2}. Since there are mm directed edges, (6.4) follows.

Repeating the argument for (6.4) gives

Pv(N>2j)(m3t02)j;j0P_{v}(N>2j)\leq\left(\frac{m^{3}}{t^{2}_{0}}\right)^{j};\ j\geq 0

and hence, assuming m3<t02m^{3}<t^{2}_{0},


Putting t0=2m3/2t_{0}=\lceil 2m^{3/2}\rceil gives EvN8/3E_{v}N\leq 8/3. Substituting into (6.3),

maxvEvCe83(2m3/2+2maxvEvC).\max_{v}E_{v}C_{e}\leq\frac{8}{3}(\lceil 2m^{3/2}\rceil+2\max_{v}E_{v}C).

Now Theorem 6.1 says maxvEvCm(n-1)mn-1\max_{v}E_{v}C\leq m(n-1)\leq mn-1, so

maxvEvCe\displaystyle\max_{v}E_{v}C_{e} \displaystyle\leq 83(2m3/2+2mn)\displaystyle\frac{8}{3}(2m^{3/2}+2mn)
=\displaystyle= 163m(m1/2+n)\displaystyle\frac{16}{3}m(m^{1/2}+n)
\displaystyle\leq 323mn\displaystyle\frac{32}{3}mn

establishing the Proposition. \Box

Another variant of Theorem 6.1, due to Kahn et al [205] (whose proof we follow), uses a graph-theoretical lemma to produce a “good” spanning tree in graphs of high degree.

Theorem 6.4

Writing d*=minvdvd_{*}=\min_{v}d_{v},

maxvEvC+6d¯n2d*\max_{v}E_{v}C^{+}\leq\frac{6\bar{d}n^{2}}{d_{*}} (6.5)

and so on a regular graph

maxvEvC+6n2.\max_{v}E_{v}C^{+}\leq 6n^{2}. (6.6)

To appreciate (6.6), consider

Example 6.5

Take an even number j2j\geq 2 cliques of size d3d\geq 3, distinguish two vertices vi,viv_{i},v^{\prime}_{i} in the ii’th clique (for each 0i<j0\leq i<j), remove the edges (vi,vi)(v_{i},v^{\prime}_{i}) and add the edges (vi,v(i+1) mod j)(v^{\prime}_{i},v_{(i+1)\mbox{ mod }j}). This creates a (d-1)(d-1)-regular graph with n=jdn=jd vertices.

Arguing as in the barbell example (Chapter 5 yyy), as dd\rightarrow\infty with jj varying arbitrarily,

maxv,wEvTwd2×d×j24n28.\max_{v,w}E_{v}T_{w}\sim\frac{d}{2}\times d\times\frac{j^{2}}{4}\sim\frac{n^{2% }}{8}.

Thus the O(n2)O(n^{2}) bound in (6.6) can’t be improved, even as a bound for the smaller quantity maxv,wEvTw\max_{v,w}E_{v}T_{w}. (Note that in the example, d/n1/2d/n\leq 1/2. From the results in Chapter 5 Example yyy and Matthews’ method one gets EC=O(nlogn)EC=O(n\log n) for regular graphs with d/nd/n bounded above 1/21/2.)

Here is the graph-theory lemma needed for the proof of Theorem 6.4.

Lemma 6.6

Let GG be an nn-vertex graph with minimal degree d*d_{*}. There exists a family of d*/2\lceil d_{*}/2\rceil spanning forests FiF_{i} such that

(i) Each edge of GG appears in at most 22 forests

(ii) Each component of each forest has size at least d*/2\lceil d_{*}/2\rceil.

Proof. Replace each edge (i,j)(i,j) of the graph by two directed edges (ij),(ji)(i\rightarrow j),\ (j\rightarrow i). Pick an arbitrary v1v_{1} and construct a path v1v2vqv_{1}\rightarrow v_{2}\rightarrow\ldots v_{q} on distinct vertices, stopping when the path cannot be extended. That is the first stage of the construction of F1F_{1}. For the second stage, pick a vertex vq+1v_{q+1} not used in the first stage and construct a path vq+1vq+2vrv_{q+1}\rightarrow v_{q+2}\rightarrow\ldots v_{r} in which no second-stage vertex is revisited, stopping when a first-stage vertex is hit or when the path cannot be extended. Continue stages until all vertices have been touched. This creates a directed spanning forest F1F_{1}. Note that all the neighbors of vqv_{q} must be amongst {v1,,vq-1}\{v_{1},\ldots,v_{q-1}\}, and so the size of the component of F1F_{1} containing v1v_{1} is at least d*+1d_{*}+1, and similarly for the other components of F1F_{1}.

Now delete from the graph all the directed edges used in F1F_{1}. Inductively construct forests F2,F3,,Fd*/2F_{2},F_{3},\ldots,F_{\lceil d_{*}/2\rceil} in the same way. The same argument shows that each component of FiF_{i} has size at least d*+2-id_{*}+2-i, because at a “stopping” vertex vv at most i-1i-1 of the directed edges out of vv were used in previous forests.

Proof of Theorem 6.4. Write mm for the number of (undirected) edges. For an edge e=(v,x)e=(v,x) write be=EvTx+ExTvb_{e}=E_{v}T_{x}+E_{x}T_{v}. Chapter 3 Lemma yyy says ebe=2m(n-1)\sum_{e}b_{e}=2m(n-1). Now consider the d*/2\lceil d_{*}/2\rceil forests FiF_{i} given by Lemma 6.6. Since each edge appears in at most two forests,

ieFibe2ebe4mn,\sum_{i}\sum_{e\in F_{i}}b_{e}\leq 2\sum_{e}b_{e}\leq 4mn,

and so there exists a forest FF with eFbe4mn/d*/28mn/d*\sum_{e\in F}b_{e}\leq 4mn/\lceil d_{*}/2\rceil\leq 8mn/d_{*}. But each component of FF has size at least d*/2\lceil d_{*}/2\rceil, so FF has at most 2n/d*2n/d_{*} components. So to extend FF to a tree 𝒯{\cal T} requires adding at most 2n/d*-12n/d_{*}-1 edges (ej)(e_{j}), and for each edge ee we have be2mb_{e}\leq 2m by (6.2). This creates a spanning tree 𝒯{\cal T} with e𝒯be12mn/d*\sum_{e\in\mbox{${\cal T}$}}b_{e}\leq 12mn/d_{*}. As in the proof of Theorem 6.1, this is an upper bound for EvC+E_{v}C^{+}.