6.1 The spanning tree argument

Except for Theorem 6.1, we consider in this section random walk on an $n$-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 $\bar{d}$:

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

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

Proof. Given a spanning tree ${\cal T}$ and a vertex $v$, there is a path $v=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

This gives the weighted case, and in the unweighted case $w=\bar{d}n$ and each spanning tree has $\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)^{2}$. On the barbell (Chapter 5 Example yyy) it is easy to see that $\min_{i}E_{i}C=\Omega(n^{3})$, so the maximal values of any formalization of “mean cover time”, over $n$-vertex graphs, is $\Theta(n^{3})$. Results and conjectures on the optimal numerical constants in the $\Theta(n^{3})$ upper bounds are given in section 6.3.

Proof. The inequality follows from Theorem 6.1. On the $n$-path with leaves $v,z$ we have $E_{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^{+}$ 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 $\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 $C$ 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.

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

and so by Wald’s identity (yyy refs)

Clearly

To estimate the other factor, we shall first show

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

Repeating the argument for (6.4) gives

and hence, assuming $m^{3}<t^{2}_{0}$,

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

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

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.

To appreciate (6.6), consider

Arguing as in the barbell example (Chapter 5 yyy), as $d\rightarrow\infty$ with $j$ varying arbitrarily,

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

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

Proof. Replace each edge $(i,j)$ of the graph by two directed edges $(i\rightarrow j),\ (j\rightarrow i)$. Pick an arbitrary $v_{1}$ and construct a path $v_{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 $F_{1}$. For the second stage, pick a vertex $v_{q+1}$ not used in the first stage and construct a path $v_{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 $F_{1}$. Note that all the neighbors of $v_{q}$ must be amongst $\{v_{1},\ldots,v_{q-1}\}$, and so the size of the component of $F_{1}$ containing $v_{1}$ is at least $d_{*}+1$, and similarly for the other components of $F_{1}$.

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

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

and so there exists a forest $F$ with $\sum_{e\in F}b_{e}\leq 4mn/\lceil d_{*}/2\rceil\leq 8mn/d_{*}$. But each component of $F$ has size at least $\lceil d_{*}/2\rceil$, so $F$ has at most $2n/d_{*}$ components. So to extend $F$ to a tree ${\cal T}$ requires adding at most $2n/d_{*}-1$ edges $(e_{j})$, and for each edge $e$ we have $b_{e}\leq 2m$ by (6.2). This creates a spanning tree ${\cal T}$ with $\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 $E_{v}C^{+}$.