We remain in the setting of random walk on an unweighted graph. Theorems 6.1 and 6.4 show that the mean cover times, and hence mean hitting times, are on irregular graphs and on regular graphs, and examples such as the barbell and the -cycle show these bounds are the right order of magnitude. Quite a lot of attention has been paid to sharpening the constants in such bounds. We will not go into details, but will merely record a very simple argument in section 6.3.1 and the best known results in section 6.3.2.
Obviously , so maximizing over gives
(6.13) |
and the results of section 6.1 imply upper bounds on . But implicit in earlier results is a direct bound on . The edge-commute inequality implies that, for arbitrary at distance ,
(6.14) |
and hence
, where is the diameter of the graph.
It is interesting to compare the implications of Corollary 6.8 with what can be deduced from (6.13) and the results of section 6.1. To bound in terms of alone, we have , and then Corollary 6.8 gives the same bound as follows from Theorem 6.1. On the other hand, the very simple graph-theoretic Lemma 6.10 gives (with Corollary 6.8) the following bound, which removes a factor of from the bound implied by Theorem 6.4.
and so on a regular graph .
.
Proof. Consider a path , where vertices and are distance apart. Write for the set of neighbors of . Then and must be disjoint when . So a given vertex can be in at most of the ’s, giving the final inequality of
Here we record results without giving proofs. Write max for the maximum over -vertex graphs. The next result is the only case where the exact extremal graph is known.
is attained by the lollipop (Chapter 5 Example yyy) with , taking to be the leaf.
Note that the implied asymptotic behavior is
(6.15) |
Further asymptotic results are given by
The value in (6.16) is asymptotically attained on the lollipop, as in Theorem 6.11. Note that (6.15) and (6.16) imply the same behavior for intermediate quantities such as and . The values in (6.17) and (6.18) are asymptotically attained by the graph consisting of a -path with a -clique attached at the middle of the path.
The corresponding results for and are not known. We have , the latter inequality from the random target lemma, and so (6.18) implies
(6.19) |
But a natural guess is that the asymptotic behavior is that of the barbell, giving the values below.
Prove the conjectures
For regular graphs, none of the asymptotic values are known exactly. A natural candidate for extremality is the necklace graph (Chapter 5 yyy), where the time parameters are asymptotically times the parameters for the -path. So the next conjecture uses the numerical values from the necklace graph.
Prove the conjectures that, over the class of regular -vertex graphs
The best bounds known are those implied by the following result.
On a -regular graph,