6 Cover Times (October 31, 1994)

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⁢(n3)O(n^{3}) on irregular graphs and O⁢(n2)O(n^{2}) on regular graphs, and examples such as the barbell and the nn-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 maxj⁡(Ei⁢Tj+Ej⁢Ti)≤Ei⁢C+\max_{j}(E_{i}T_{j}+E_{j}T_{i})\leq E_{i}C^{+}, so maximizing over ii gives

τ*≤maxi⁡Ei⁢C+\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,xv,x at distance Δ⁢(v,x)\Delta(v,x),

Ev⁢Tx+Ex⁢Tv≤d¯⁢n⁢Δ⁢(v,x)E_{v}T_{x}+E_{x}T_{v}\leq\bar{d}n\Delta(v,x) (6.14)

and hence

Corollary 6.8

τ*≤d¯⁢n⁢Δ\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 nn alone, we have Δ≤n-1\Delta\leq n-1, and then Corollary 6.8 gives the same bound τ*≤d¯⁢n⁢(n-1)\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 22 from the bound implied by Theorem 6.4.

Corollary 6.9

τ*≤3⁢d¯⁢n2d*\tau^{*}\leq\frac{3\bar{d}n^{2}}{d_{*}} and so on a regular graph τ*≤3⁢n2\tau^{*}\leq 3n^{2}.

Lemma 6.10

Δ≤3⁢n/d*\Delta\leq 3n/d_{*}.

Proof. Consider a path v0,v1,…,vΔv_{0},v_{1},\ldots,v_{\Delta}, where vertices v0v_{0} and vΔv_{\Delta} are distance Δ\Delta apart. Write AiA_{i} for the set of neighbors of viv_{i}. Then AiA_{i} and AjA_{j} must be disjoint when |j-i|≥3|j-i|\geq 3. So a given vertex can be in at most 33 of the AA’s, giving the final inequality of

(Δ+1)d*≤∑i=0Δdvi=∑i=0Δ|Ai|≤3n.       □(\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 nn-vertex graphs. The next result is the only case where the exact extremal graph is known.

Theorem 6.11 (Brightwell-Winkler [62])

𝐦𝐚𝐱⁢maxv,x⁡Ev⁢Tx{\bf max}\ \max_{v,x}E_{v}T_{x}is attained by the lollipop (Chapter 5 Example yyy) with m1=⌊(2⁢n+1)/3⌋m_{1}=\lfloor(2n+1)/3\rfloor, taking xx to be the leaf.

Note that the implied asymptotic behavior is

𝐦𝐚𝐱⁢maxv,w⁡Ev⁢Tw∼427⁢n3.{\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])
𝐦𝐚𝐱⁢maxv⁡Ev⁢C+∼427⁢n3{\bf max}\max_{v}E_{v}C^{+}\sim\frac{4}{27}n^{3} (6.16)
𝐦𝐚𝐱⁢minv⁡Ev⁢C+∼327⁢n3{\bf max}\min_{v}E_{v}C^{+}\sim\frac{3}{27}n^{3} (6.17)
𝐦𝐚𝐱⁢minv⁡Ev⁢C∼227⁢n3{\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 4⁢n3/274n^{3}/27 behavior for intermediate quantities such as τ*\tau^{*} and maxv⁡Ev⁢C\max_{v}E_{v}C. The values in (6.17) and (6.18) are asymptotically attained by the graph consisting of a n/3n/3-path with a 2⁢n/32n/3-clique attached at the middle of the path.

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

𝐦𝐚𝐱⁢τ0⁢ and ⁢𝐦𝐚𝐱⁢τ2≤(227+o⁢(1))⁢n3.{\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

𝐦𝐚𝐱⁢τ0∼154⁢n3,   𝐦𝐚𝐱⁢τ2∼154⁢n3.{\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/43/4 times the parameters for the nn-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 nn-vertex graphs

𝐦𝐚𝐱⁢maxi,j⁡Ei⁢Tj∼34⁢n2{\bf max}\max_{i,j}E_{i}T_{j}\sim\frac{3}{4}n^{2}
𝐦𝐚𝐱⁢τ*∼32⁢n2{\bf max}\ \tau^{*}\sim\frac{3}{2}n^{2}
𝐦𝐚𝐱⁢maxv⁡Ev⁢C+∼32⁢n2{\bf max}\max_{v}E_{v}C^{+}\sim\frac{3}{2}n^{2}
𝐦𝐚𝐱⁢maxv⁡Ev⁢C∼1516⁢n2{\bf max}\max_{v}E_{v}C\sim\frac{15}{16}n^{2}
𝐦𝐚𝐱⁢minv⁡Ev⁢C∼34⁢n2{\bf max}\min_{v}E_{v}C\sim\frac{3}{4}n^{2}
𝐦𝐚𝐱⁢τ0∼14⁢n2{\bf max}\ \tau_{0}\sim\frac{1}{4}n^{2}
𝐦𝐚𝐱⁢τ2∼32⁢π2⁢n2{\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 dd-regular graph,

maxv⁡Ev⁢C≤\displaystyle\max_{v}E_{v}C\leq 2⁢n2\displaystyle 2n^{2}
maxv⁡Ev⁢Cv+≤\displaystyle\max_{v}E_{v}C^{+}_{v}\leq 2⁢n2⁢(1+d-2(d+1)2)\displaystyle 2n^{2}\left(1+\frac{d-2}{(d+1)^{2}}\right) ≤13⁢n2/6.\displaystyle\leq 13n^{2}/6.
Bibliography