6 Cover Times (October 31, 1994)

6.9 Notes on Chapter 6

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 beb_{e} for the mean commute time across an edge ee, that

maxvEvC+min𝒯e𝒯be.\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γ/310\gamma/3, where


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 VV on the nn-cycle, are essentially classical. For the cover time CnC_{n} on the nn-cycle there is a non-degenerate limit distribution n-2CndCn^{-2}C_{n}\ \stackrel{d}{\rightarrow}\ C. From the viewpoint of weak convergence (Chapter yyy), CC 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

fC(t)=23/2π-1/2t-3/2m=1(-1)m-1m2exp(-m22t).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 fCf_{C}.

Section 6.4. Use of Lemma 6.10 in the random walk context goes back at least to Flatto et al [152].

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(ν2logν)O(\nu^{2}\log\nu) on regular graphs.

Proposition 6.18 implies that on an infinite regular graph Pi(Xt=j)Kt-1/2P_{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 Pi(X2t=i)+Pi(X2t+1=i)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 τ1(1)\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 τ2\tau_{2} via the general inequalities τ2τ012τ*\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 τ2\tau_{2} directly. For instance, in the setting of a dd-regular rr-edge-connected graph, a direct bound (Chapter 4 Proposition yyy) gives


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

xxx contrast with potential and Cheeger-like arguments ?

To sketch an example of a regular graph where miniEiC\min_{i}E_{i}C has a different order than maxiEiC\max_{i}E_{i}C, make a regular m1+m2m_{1}+m_{2}-vertex graph from a m1m_{1}-vertex graph with mean cover time Θ(m1logm1)\Theta(m_{1}\log m_{1}) and a m2m_{2}-vertex graph (such as the necklace) with mean cover time Θ(m22)\Theta(m_{2}^{2}), for suitable values of the mm’s. Starting from a typical vertex of the former, the mean cover time is Θ(m1logm1+m1m2+m22)\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 Θ(m1logm1+m22)\Theta(m_{1}\log m_{1}+m_{2}^{2}). Taking m1logm1+m22)=o(m1m2)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

minvEvC(1+o(1))nlog2n2log(d*-1) if d*maxvdv=no(1).\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.

The “shorting” lower bound, Lemma 6.28, was apparently first exploited by Coppersmith et al [100].

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 (ct)(c_{t}) of colors is prespecified and the “random walk” at step tt picks an edge uniformly at random from the color-ctc_{t} edges at the current vertex.