Attributions for what I regard as the main ideas were given in the text. The literature contains a number of corollaries or variations of these ideas, some of which I’ve used without attribution, and many of which I haven’t mentioned at all. A number of these ideas can be found in Zuckerman [341, 343], Palacios [276, 273] and the Ph.D. thesis of Sbihi [306], as well as papers cited elsewhere.

Section 6.1. The conference proceedings paper [25] proving Theorem 6.1 was not widely known, or at least its implications not realized, for some years. Several papers subsequently appeared proving results which are consequences (either obvious, or via the general relations of Chapter 4) of Theorem 6.1. I will spare their authors embarrassment by not listing them all here!

The spanning tree argument shows, writing $b_{e}$ for the mean commute time across an edge $e$, that

$\max_{v}E_{v}C^{+}\leq\min_{\mbox{${\cal T}$}}\sum_{e\in\mbox{${\cal T}$}}b_{e}.$ |

Coppersmith et al [100] give a deeper study and show that the right side is bounded between $\gamma$ and $10\gamma/3$, where

$\gamma=\left(\sum_{v}d_{v}\right)\left(\sum_{v}\frac{1}{d_{v}+1}\right).$ |

The upper bound is obtained by considering a random spanning tree, cf. Chapter yyy.

Section 6.2. The calculations in these examples, and the uniformity property of $V$ on the $n$-cycle, are essentially classical. For the cover time $C_{n}$ on the $n$-cycle there is a non-degenerate limit distribution $n^{-2}C_{n}\ \stackrel{d}{\rightarrow}\ C$. From the viewpoint of weak convergence (Chapter yyy), $C$ is just the cover time for Brownian motion on the circle of unit circumference, and its distribution is known as part of a large family of known distributions for maximal-like statistics of Brownian motion: Imhof [187] eq. (2.4) gives the density as

$f_{C}(t)=2^{3/2}\pi^{-1/2}t^{-3/2}\sum_{m=1}^{\infty}(-1)^{m-1}m^{2}\exp(-% \frac{m^{2}}{2t}).$ |

Sbihi [306] gives a direct derivation of a different representation of $f_{C}$.

Barnes and Feige [42] give a more extensive treatment of short-time bounds in the irregular setting, and their applications to covering with multiple walks (cf. Proposition 6.17 and section 6.8.2). They also give bounds on the mean time taken to cover $\mu$ different edges or $\nu$ different vertices – their bound for the latter becomes $O(\nu^{2}\log\nu)$ on regular graphs.

Proposition 6.18 implies that on an infinite regular graph $P_{i}(X_{t}=j)\leq Kt^{-1/2}$. Carlen et al [84] Theorem 5.14 prove this as a corollary of results using more sophisticated machinery. Our argument shows the result is fairly elementary. In discrete time the analog of the first inequality can be proved using the “CM proxy” property than $P_{i}(X_{2t}=i)+P_{i}(X_{2t+1}=i)$ is decreasing, but the analog of the second inequality requires different arguments because we cannot exploit the $\tau_{1}^{(1)}$ inequalities.

Section 6.5. Variations on Corollary 6.21 are given in Broder and Karlin [65] and Chandra et al. [85].

Upper bounds on mean hitting times imply upper bounds on the relaxation time $\tau_{2}$ via the general inequalities $\tau_{2}\leq\tau_{0}\leq\frac{1}{2}\tau^{*}$. In most concrete examples these bounds are too crude to be useful, but in “extremal” settings these bounds are essentially as good as results seeking to bound $\tau_{2}$ directly. For instance, in the setting of a $d$-regular $r$-edge-connected graph, a direct bound (Chapter 4 Proposition yyy) gives

$\tau_{2}\leq\frac{d}{4r\sin^{2}\frac{\pi}{2n}}\sim\frac{dn^{2}}{\pi^{2}r}.$ |

Up to the numerical constant, the same bound is obtained from Proposition 6.22 and the general inequality $\tau_{2}\leq\tau^{*}/2$.

xxx contrast with potential and Cheeger-like arguments ?

To sketch an example of a regular graph where $\min_{i}E_{i}C$ has a different order than $\max_{i}E_{i}C$, make a regular $m_{1}+m_{2}$-vertex graph from a $m_{1}$-vertex graph with mean cover time $\Theta(m_{1}\log m_{1})$ and a $m_{2}$-vertex graph (such as the necklace) with mean cover time $\Theta(m_{2}^{2})$, for suitable values of the $m$’s. Starting from a typical vertex of the former, the mean cover time is $\Theta(m_{1}\log m_{1}+m_{1}m_{2}+m_{2}^{2})$ whereas starting from the unattached end of the necklace the mean cover time is $\Theta(m_{1}\log m_{1}+m_{2}^{2})$. Taking $m_{1}\log m_{1}+m_{2}^{2})=o(m_{1}m_{2})$ gives the desired example.

Section 6.6. The “subset” version of Matthews’ lower bound (Theorem 2.6) and its application to trees were noted by Zuckerman [343], Sbihi [306] and others. As well as giving a lower bound for balanced trees, these authors give several lower bounds for more general trees satisfying various constraints (cf. the unconstrained result, Proposition 6.7). As an illustration, Devroye - Sbihi [110] show that on a tree

$\min_{v}E_{v}C\geq\frac{(1+o(1))n\log^{2}n}{2\log(d^{*}-1)}\mbox{ if }d^{*}% \equiv\max_{v}d_{v}=n^{o(1)}.$ |

I believe that the recursion set-up in [21] can be used to prove Open Problem 6.35 on trees, but I haven’t thought carefully about it.

Section 6.7. Corollary 6.32 encompasses a number of exponential limit results proved in the literature by ad hoc calculations in particular examples.

Section 6.8.1. Proposition 6.34 is one of the neatest instances of “Erdos’s Probabilistic Method in Combinatorics”, though surprisingly it isn’t in the recent book [28] on that subject. Constructing explicit universal traversal sequences is a hard open problem: see Borodin et al [56] for a survey.

Section 6.8.2. See [64] for a more careful discussion of the issues. The alert reader of our example will have noticed the subtle implication that the reader has written fewer papers than Paul Erdos, otherwise (why?) it would be preferable to do the random walk in the other direction.

Miscellaneous. Condon and Hernek [98] study cover times in the following setting. The edges of a graph are colored, a sequence $(c_{t})$ of colors is prespecified and the “random walk” at step $t$ picks an edge uniformly at random from the color-$c_{t}$ edges at the current vertex.

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