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 $O(n^{3})$ on irregular graphs and $O(n^{2})$ on regular graphs, and examples such as the barbell and the $n$-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 $\max_{j}(E_{i}T_{j}+E_{j}T_{i})\leq E_{i}C^{+}$, so maximizing over $i$ gives

$\tau^{*}\leq\max_{i}E_{i}C^{+}$ | (6.13) |

and the results of section 6.1 imply upper bounds on $\tau^{*}$. But implicit in earlier results is a direct bound on $\tau^{*}$. The edge-commute inequality implies that, for arbitrary $v,x$ at distance $\Delta(v,x)$,

$E_{v}T_{x}+E_{x}T_{v}\leq\bar{d}n\Delta(v,x)$ | (6.14) |

and hence

$\tau^{*}\leq\bar{d}n\Delta$, where $\Delta$ 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 $\Delta$ in terms of $n$ alone, we have $\Delta\leq n-1$, and then Corollary 6.8 gives the same bound $\tau^{*}\leq\bar{d}n(n-1)$ 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 $2$ from the bound implied by Theorem 6.4.

$\tau^{*}\leq\frac{3\bar{d}n^{2}}{d_{*}}$ and so on a regular graph $\tau^{*}\leq 3n^{2}$.

$\Delta\leq 3n/d_{*}$.

Proof. Consider a path $v_{0},v_{1},\ldots,v_{\Delta}$, where vertices $v_{0}$ and $v_{\Delta}$ are distance $\Delta$ apart. Write $A_{i}$ for the set of neighbors of $v_{i}$. Then $A_{i}$ and $A_{j}$ must be disjoint when $|j-i|\geq 3$. So a given vertex can be in at most $3$ of the $A$’s, giving the final inequality of

$(\Delta+1)d_{*}\leq\sum_{i=0}^{\Delta}d_{v_{i}}=\sum_{i=0}^{\Delta}|A_{i}|\leq 3% n.\ \ \ \ \ \ \ \ \ \ \ \Box$ |

Here we record results without giving proofs. Write max for the maximum over $n$-vertex graphs. The next result is the only case where the exact extremal graph is known.

${\bf max}\ \max_{v,x}E_{v}T_{x}$is attained by the lollipop (Chapter 5 Example yyy) with $m_{1}=\lfloor(2n+1)/3\rfloor$, taking $x$ to be the leaf.

Note that the implied asymptotic behavior is

${\bf max}\ \max_{v,w}E_{v}T_{w}\sim\frac{4}{27}n^{3}.$ | (6.15) |

Further asymptotic results are given by

${\bf max}\max_{v}E_{v}C^{+}\sim\frac{4}{27}n^{3}$ | (6.16) |

${\bf max}\min_{v}E_{v}C^{+}\sim\frac{3}{27}n^{3}$ | (6.17) |

${\bf max}\min_{v}E_{v}C\sim\frac{2}{27}n^{3}$ | (6.18) |

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 $4n^{3}/27$ behavior for intermediate quantities such as $\tau^{*}$ and $\max_{v}E_{v}C$. The values in (6.17) and (6.18) are asymptotically attained by the graph consisting of a $n/3$-path with a $2n/3$-clique attached at the middle of the path.

The corresponding results for $\tau_{0}$ and $\tau_{2}$ are not known. We have $\tau_{2}\leq\tau_{0}\leq\min_{v}E_{v}C$, the latter inequality from the random target lemma, and so (6.18) implies

${\bf max}\tau_{0}\mbox{ and }{\bf max}\tau_{2}\ \leq(\frac{2}{27}+o(1))n^{3}.$ | (6.19) |

But a natural guess is that the asymptotic behavior is that of the barbell, giving the values below.

Prove the conjectures

${\bf max}\ \tau_{0}\sim\frac{1}{54}n^{3},\ \ \ {\bf max}\ \tau_{2}\sim\frac{1}% {54}n^{3}.$ |

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 $3/4$ times the parameters for the $n$-path. So the next conjecture uses the numerical values from the necklace graph.

Prove the conjectures that, over the class of regular $n$-vertex graphs

${\bf max}\max_{i,j}E_{i}T_{j}\sim\frac{3}{4}n^{2}$ |

${\bf max}\ \tau^{*}\sim\frac{3}{2}n^{2}$ |

${\bf max}\max_{v}E_{v}C^{+}\sim\frac{3}{2}n^{2}$ |

${\bf max}\max_{v}E_{v}C\sim\frac{15}{16}n^{2}$ |

${\bf max}\min_{v}E_{v}C\sim\frac{3}{4}n^{2}$ |

${\bf max}\ \tau_{0}\sim\frac{1}{4}n^{2}$ |

${\bf max}\ \tau_{2}\sim\frac{3}{2\pi^{2}}n^{2}$ |

The best bounds known are those implied by the following result.

On a $d$-regular graph,

$\displaystyle\max_{v}E_{v}C\leq$ | $\displaystyle 2n^{2}$ | |||

$\displaystyle\max_{v}E_{v}C^{+}_{v}\leq$ | $\displaystyle 2n^{2}\left(1+\frac{d-2}{(d+1)^{2}}\right)$ | $\displaystyle\leq 13n^{2}/6.$ |

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