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 -vertex graphs with , consider the property
(6.28) |
(in this order-of-magnitude discussion, is equivalent to ). Recalling from Chapter 3 yyy that , we see that (6.28) is equivalent to . By Matthews’ method (repeated as Theorem 2.6 below), (6.28) implies , and then by Theorem 6.31 we have . 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 -dimensional torus (Chapter 5 Example yyy), where (6.28) holds iff . 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 dimensions”) may be sufficient.
Show that for real and , there exists a constant with the following property. Let be a regular -vertex graph such that, for any subset of vertices with , there exist at least edges between and . Then .
The case is implicit in results from previous chapters. Chapter 3 yyy gave the bound , and Chapter 3 yyy gave the bound . This gives the first assertion below, and the second follows from Cheeger’s inequality.
On a regular graph,
Thus the “expander” property that , or equivalently that , is sufficient for (6.28), and the latter is the case of Open Problem 6.20.
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 -edge-connected if for each proper subset of vertices there are at least edges linking with . By a variant of Menger’s theorem (e.g. [86] Theorem 5.11), for each pair of vertices in such a graph, there exist paths , for which the edges are all distinct.
For a -edge-connected graph,
where is defined by
Note . So for a -regular, -edge-connected graph, the bound becomes for large , 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 , construct a unit flow from to by putting flow along each of the paths . By Chapter 3 Theorem yyy
where is the total number of edges in the paths. So the issue is bounding . Consider the digraph of all edges . If this digraph contained a directed cycle, we could eliminate the edges on that cycle, and still create paths from to using the remaining edges. So we may assume the digraph is acyclic, which implies we can label the vertices as in such a way that each edge has . So the desired result follows from
In a digraph on vertices consisting of paths and where all edges are distinct, the total number of edges is at most .
Proof.
xxx give proof and picture.
Take vertices and edges for all and all .
This example highlights the “slack” in Proposition 6.22. Regard as large and fixed, and . Random walk on this graph is classical random walk (i.e. sums of independent steps) on the -cycle, where the steps have variance , and it is easy to see
This is the bound Proposition 6.22 would give if the graph were -edge-connected. And for a “typical” subset such as an interval of length greater than there are indeed edges crossing the boundary of . But by considering a singleton we see that the graph is really only -edge-connected, and Proposition 6.22 gives only the weaker bound.
xxx tie up with similar discussion of and connectivity being affected by small sets; better than bound using only.
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.
The parameters , , , and are equivalent for reversible chains, but is not equivalent to these.
Proof. Of the five parameters asserted to be equivalent, it is clear that is the largest, and that either or is the smallest, so it suffices to prove
(6.29) |
(6.30) |
Inequality (6.30) holds by concatenating three “cover-and-return” cycles starting at and considering the first hitting time on in the first and third cycles. In more detail, write
For the chain started at write and . Since we have . So the chain started at time has covered all states and returned to by time , implying . For inequality (6.29), recall the random target lemma: the mean time to hit a -random state equals , regardless of the initial distribution. The inequality
follows from the four-step construction:
(i) Start the chain at and run until hitting a -random vertex
at time ;
(ii) continue until time ;
(iii) continue until hitting an independent -random vertex ;
(iv) continue until hitting .
But , and then by the random target lemma
, so (6.29) follows.
For the final assertion, on the lollipop graph (Chapter 5 Example yyy) one has while the other quantities are . One can also give examples on regular graphs (see Notes).