6 Cover Times (October 31, 1994)

6.5 Hitting time bounds and connectivity

The results so far in this chapter may be misleading in that upper bounds accommodating extremal graphs are rather uninformative for “typical” graphs. For a family of nn-vertex graphs with nn\rightarrow\infty, consider the property

τ*=O(n).\tau^{*}=O(n). (6.28)

(in this order-of-magnitude discussion, τ*\tau^{*} is equivalent to maxv,xEvTx\max_{v,x}E_{v}T_{x}). Recalling from Chapter 3 yyy that τ*2(n-1)\tau^{*}\geq 2(n-1), we see that (6.28) is equivalent to τ*=Θ(n)\tau^{*}=\Theta(n). By Matthews’ method (repeated as Theorem 2.6 below), (6.28) implies EC=O(nlogn)EC=O(n\log n), and then by Theorem 6.31 we have EC=Θ(nlogn)EC=\Theta(n\log n). Thus understanding when (6.28) holds is fundamental to understanding order-of-magnitude questions about cover times. But surprisingly, this question has not been studied very carefully. An instructive example in the dd-dimensional torus (Chapter 5 Example yyy), where (6.28) holds iff d3d\geq 3. This example, and other examples of vertex-transitive graphs satisfying (6.28) discussed in Chapter 8, suggest that (6.28) is frequently true. More concretely, the torus example suggests that the following condition (“the isoperimetric property in 2+ε2+\varepsilon dimensions”) may be sufficient.

Open Problem 6.20

Show that for real 1/2<γ<11/2<\gamma<1 and δ>0\delta>0, there exists a constant Kγ,δK_{\gamma,\delta} with the following property. Let GG be a regular nn-vertex graph such that, for any subset AA of vertices with |A|n/2|A|\leq n/2, there exist at least δ|A|γ\delta|A|^{\gamma} edges between AA and AcA^{c}. Then τ*Kγ,δn\tau^{*}\leq K_{\gamma,\delta}\ n.

The γ=1\gamma=1 case is implicit in results from previous chapters. Chapter 3 yyy gave the bound maxi,jEiTj2maxjEπTj\max_{i,j}E_{i}T_{j}\leq 2\max_{j}E_{\pi}T_{j}, and Chapter 3 yyy gave the bound EπTjτ2/πjE_{\pi}T_{j}\leq\tau_{2}/\pi_{j}. This gives the first assertion below, and the second follows from Cheeger’s inequality.

Corollary 6.21

On a regular graph,

maxv,xEvTx2nτ216nτc2.\max_{v,x}E_{v}T_{x}\leq 2n\tau_{2}\leq 16n\tau^{2}_{c}.

Thus the “expander” property that τ2=O(1)\tau_{2}=O(1), or equivalently that τc=O(1)\tau_{c}=O(1), is sufficient for (6.28), and the latter is the γ=1\gamma=1 case of Open Problem 6.20.

6.5.1 Edge-connectivity

At the other end of the spectrum from expanders, we can consider graphs satisfying only a little more than connectivity.

xxx more details in proofs – see Fill’s comments.

Recall that a graph is rr-edge-connected if for each proper subset AA of vertices there are at least rr edges linking AA with AcA^{c}. By a variant of Menger’s theorem (e.g. [86] Theorem 5.11), for each pair (a,b)(a,b) of vertices in such a graph, there exist rr paths (a=v0i,v1i,v2i,,vmii=b)(a=v^{i}_{0},v^{i}_{1},v^{i}_{2},\ldots,v^{i}_{m_{i}}=b), i=1,,ri=1,\ldots,r for which the edges (vji,vj+1i)(v^{i}_{j},v^{i}_{j+1}) are all distinct.

Proposition 6.22

For a rr-edge-connected graph,


where ψ\psi is defined by

ψ() is linear on [i(i+1)2,(i+1)(i+2)2].\psi(\cdot)\mbox{ is linear on }\left[\frac{i(i+1)}{2},\frac{(i+1)(i+2)}{2}% \right].

Note ψ(r)2r\psi(r)\sim\sqrt{2r}. So for a dd-regular, dd-edge-connected graph, the bound becomes 21/2d-1/2n2\sim 2^{1/2}d^{-1/2}n^{2} for large dd, improving on the bound from Corollary 6.9. Also, the Proposition improves on the bound implied by Chapter 4 yyy in this setting.

Proof. Given vertices a,ba,b, construct a unit flow from aa to bb by putting flow 1/r1/r along each of the rr paths (a=v0i,v1i,v2i,,vmii=b)(a=v^{i}_{0},v^{i}_{1},v^{i}_{2},\ldots,v^{i}_{m_{i}}=b). By Chapter 3 Theorem yyy


where M=imiM=\sum_{i}m_{i} is the total number of edges in the rr paths. So the issue is bounding MM. Consider the digraph of all edges (vji,vj+1i)(v^{i}_{j},v^{i}_{j+1}). If this digraph contained a directed cycle, we could eliminate the edges on that cycle, and still create rr paths from aa to bb using the remaining edges. So we may assume the digraph is acyclic, which implies we can label the vertices as a=1,2,3,,n=ba=1,2,3,\ldots,n=b in such a way that each edge (j,k)(j,k) has k>jk>j. So the desired result follows from

Lemma 6.23

In a digraph on vertices {1,2,,n}\{1,2,\ldots,n\} consisting of rr paths 1=v0i<v1i<v2i<vmii=n1=v^{i}_{0}<v^{i}_{1}<v^{i}_{2}<\ldots v^{i}_{m_{i}}=n and where all edges are distinct, the total number of edges is at most nψ(r)n\psi(r).


xxx give proof and picture.

Example 6.24

Take vertices {0,1,,n-1}\{0,1,\ldots,n-1\} and edges (i,i+u mod n)(i,i+u\mbox{ mod }n) for all ii and all 1uκ1\leq u\leq\kappa.

This example highlights the “slack” in Proposition 6.22. Regard κ\kappa as large and fixed, and nn\rightarrow\infty. Random walk on this graph is classical random walk (i.e. sums of independent steps) on the nn-cycle, where the steps have variance σ2=1κu=1κu2\sigma^{2}=\frac{1}{\kappa}\sum_{u=1}^{\kappa}u^{2}, and it is easy to see

τ*=2E0Tn/2(n/2)2σ2=Θ(n2/κ2).\tau^{*}=2E_{0}T_{\lfloor n/2\rfloor}\sim\frac{(n/2)^{2}}{\sigma^{2}}=\Theta(n% ^{2}/\kappa^{2}).

This is the bound Proposition 6.22 would give if the graph were Θ(κ2)\Theta(\kappa^{2})-edge-connected. And for a “typical” subset AA such as an interval of length greater than κ\kappa there are indeed Ω(κ2)\Omega(\kappa^{2}) edges crossing the boundary of AA. But by considering a singleton AA we see that the graph is really only 2κ2\kappa-edge-connected, and Proposition 6.22 gives only the weaker O(n2/κ1/2)O(n^{2}/\kappa^{1/2}) bound.

xxx tie up with similar discussion of τ2\tau_{2} and connectivity being affected by small sets; better than bound using τc\tau_{c} only.

6.5.2 Equivalence of mean cover time parameters

Returning to the order-of-magnitude discussion at the start of section 6.5, let us record the simple equivalence result. Recall (cf. Chapter 4 yyy) we call parameters equivalent if their ratios are bounded by absolute constants.

Lemma 6.25

The parameters maxiEiC+\max_{i}E_{i}C^{+}, EπC+E_{\pi}C^{+}, miniEiC+\min_{i}E_{i}C^{+}, maxiEiC\max_{i}E_{i}C and EπCE_{\pi}C are equivalent for reversible chains, but miniEiC\min_{i}E_{i}C is not equivalent to these.

Proof. Of the five parameters asserted to be equivalent, it is clear that maxiEiC\max_{i}E_{i}C is the largest, and that either miniEiC+\min_{i}E_{i}C^{+} or EπCE_{\pi}C is the smallest, so it suffices to prove

maxiEiC+4EπC\max_{i}E_{i}C^{+}\leq 4E_{\pi}C (6.29)
maxjEjC+3miniEiC+.\max_{j}E_{j}C^{+}\leq 3\min_{i}E_{i}C^{+}. (6.30)

Inequality (6.30) holds by concatenating three “cover-and-return” cycles starting at ii and considering the first hitting time on jj in the first and third cycles. In more detail, write

Γ(s)=min{u>s:(Xt:stu) covers all states}.\Gamma(s)=\min\{u>s:(X_{t}:s\leq t\leq u)\mbox{ covers all states}\}.

For the chain started at ii write C++=Γ(C+)C^{++}=\Gamma(C^{+}) and C+++=Γ(C++)C^{+++}=\Gamma(C^{++}). Since Tj<C+T_{j}<C^{+} we have Γ(Tj)C++\Gamma(T_{j})\leq C^{++}. So the chain started at time TjT_{j} has covered all states and returned to jj by time C+++C^{+++}, implying EjC+EC+++=3EiC+E_{j}C^{+}\leq EC^{+++}=3E_{i}C^{+}. For inequality (6.29), recall the random target lemma: the mean time to hit a π\pi-random state VV equals τ0\tau_{0}, regardless of the initial distribution. The inequality


follows from the four-step construction:

(i) Start the chain at ii and run until hitting a π\pi-random vertex VV at time TVT_{V};

(ii) continue until time Γ(TV)\Gamma(T_{V});

(iii) continue until hitting an independent π\pi-random vertex VV^{\prime};

(iv) continue until hitting ii.

But EπTiEπCE_{\pi}T_{i}\leq E_{\pi}C, and then by the random target lemma τ0EπC\tau_{0}\leq E_{\pi}C, so (6.29) follows.

For the final assertion, on the lollipop graph (Chapter 5 Example yyy) one has miniEiC=Θ(n2)\min_{i}E_{i}C=\Theta(n^{2}) while the other quantities are Θ(n3)\Theta(n^{3}). One can also give examples on regular graphs (see Notes).