# 6.3 More upper bounds

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.

## 6.3.1 Simple upper bounds for mean hitting times

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

###### Corollary 6.8

$\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.

###### Corollary 6.9

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

###### Lemma 6.10

$\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$

## 6.3.2 Known and conjectured upper bounds

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.

###### Theorem 6.11 (Brightwell-Winkler [62])

${\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

###### Theorem 6.12 (Feige [143, 144])
 ${\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.

###### Open Problem 6.13

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.

###### Open Problem 6.14

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.

###### Theorem 6.15 (Feige [144])

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.$