# Sandwich Theorem of Cover Times

Authors: Yilun Shang
Journal: ISRN Probability and Statistics
 (2013)

---

## Abstract

Based on a connection between cover times of graphs and Talagrand’s theory of majorizing measures, we establish sandwich theorems for cover times as well as blanket times.


---

## Body

## 1. Introduction

LetG=(V,E) be a connected graph with n vertices and m edges. Consider a simple random walk on G: we start at a vertex v∈V; if at step t we are at vertex u, then we move from u to a neighbor at step t+1 with probability du-1, where du is the degree of u. Let Ev be the expectation operator governing the random walk started at vertex v∈V. The cover time of G is defined as
(1)c(G)=maxv∈VEvμ(G),
where μ(G) is the first time t≥1 that all vertices of G have been traversed [1].Another relevant quantity is the strongδ-blanket time [2]. For v∈V, let πv=dv/2m be the stationary measure of the random walk, and let rv,t be the number of visits to v up to time t. For δ∈(0,1), the strong δ-blanket time is defined as
(2)b(G,δ)=maxv∈VEvτ(δ),
where τ(δ) is the first time t≥1 such that
(3)ru,t/πurv,t/πv≥δ,
holds for any two vertices u and v. Clearly, we have b(G,δ)≥c(G) for any δ∈(0,1). We refer the reader to [1, 3] for more background information on random walks.Recently, Ding et al. [4] established an important connection between cover times (blanket times) and the γ2 functional from Talagrand’s theory of majorizing measures [5, 6]; see Theorem 1. We first review the γ2 functional in brief. Consider a compact metric space (X,d), and let M0=1, Mk=22k for k≥1. For a partition 𝒫 of X and an element x∈X, denote by 𝒫(x) the unique set S∈𝒫 containing x. An admissible sequence {𝒜k}k≥0 of partitions of X is that 𝒜k+1 is a refinement of 𝒜k, and |𝒜k|≤Mk for k≥0. The γ2 functional is defined as
(4)γ2(X,d)=inf{𝒜k}supx∈X∑k=0∞‍2k/2diam(𝒜k(x)),
where diam(S) represents the diameter of S, that is, diam(S)=supx,y∈Sd(x,y). Throughout the paper, we view graph G as a metric space with distance induced by the commute time κG(u,v) between two vertices u,v∈V. Hence, (V,κG) is a compact metric space.Theorem 1 (see [4]).
For any graphG=(V,E) and δ∈(0,1),
(5)c(G)≍(γ2(V,κG))2≍δb(G,δ),
where A≍B means C1B≤A≤C2B for some constants C1,C2, and furthermore, A≍δB emphasizes that the constants may depend on δ. Here, κG(u,v)=κG(u,v).A comparison theorem for cover times is also presented.Theorem 2 (see [4]).
Suppose that graphsG and G′ are on the same vertex set V, and κG and κG′ are the distances induced by respective commute times. If there exists a number L≥1 such that κG(u,v)≤L·κG′(u,v) for all u,v∈V, then
(6)c(G)≤O(L)·c(G′).In this paper, we extend this nice comparison theorem and provide several applications.


## 2. Results

We have the following results.Theorem 3.
Suppose that three graphsG, G1, and G2 are on the same vertex set V and that κG, κG1, and κG2 are the distances induced by respective commute times. If there exist α∈(0,1], L1>0, and L2>0 such that L1·κG1(u,v)α≤κG(u,v)≤L2·κG2(u,v) for all u,v∈V, then
(7)O(L1)·c(G1)α≤c(G)≤O(L2)·c(G2).Proof.
From the assumption, we have(8)L1·κG1(u,v)α/2≤κG(u,v)≤L2·κG2(u,v),
for all vertices u and v. Capitalizing on the Cr-inequality, which says that
(9)(∑i=1n‍xi)r≤Cr(∑i=1n‍xir),
where Cr=1 if r∈(0,1] and Cr=nr-1 if r∈(1,∞), we obtain
(10)L1·γ2(V,κG1)α≤γ2(V,κG)≤L2·γ2(V,κG2)
by using definition (4).
It follows from Theorem1 that
(11)O(L1)·c(G1)α≤c(G)≤O(L2)·c(G2)
as desired.Generally, the conditions imposed on commute times in Theorem3 are thorny, if possible, to test, especially for complex and large-scale graphs. However, commute times for recursive graphs are likely to be estimated (see, e.g., [7]).Based on this comparison characterization, we have the following bounds regarding the ratio of cover times.Corollary 4.
Maintaining the notations of Theorem3, if G1=G2, one has
(12)O(L1)(maxu,v∈VH(u,v))1-α(1+lnn)1-α≤c(G)c(G1)≤O(L2),
where H(u,v) is the expected hitting time from u to v in G1.Proof.
IfG1=G2, we obtain
(13)O(L1)·c(G1)α≤c(G)≤O(L2)·c(G1).
An upper bound of cover time [8] yields
(14)O(L1)(maxu,v∈VH(u,v))1-α(1+lnn)1-α≤O(L1)c(G1)1-αO(L1)(maxu,v∈VH(u,v))1-α(1+lnn)1-α≤c(G)c(G1)≤O(L2),
where n=|V| as mentioned before.The following result is a “sandwich theorem” for monotonic graph sequences.Corollary 5.
Maintaining the notations of Theorem3, if G1 is a graph obtained by deleting an edge from G and G2 is obtained by adding an edge to G, one has
(15)O(mm+1)·c(G2)≤c(G)≤O(mm-1)·c(G1),
where m=|E| is the number of edges in G.Proof.
SinceG1 and G2 have m-1 and m+1 edges, respectively, we obtain by [3, Theorem 2.9] that
(16)mm+1κG2(u,v)≤κG(u,v)≤mm-1κG1(u,v),
for any u,v∈V. Thus, the result follows directly from Theorem 3 by taking α=1.We mention that it is recently shown in [9] that c(G2)/4≤c(G). We conclude the paper with a result on δ-strong blanket times analogous to our main theorem.Corollary 6.
Maintaining the notations of Theorem3, for any δ∈(0,1), one has
(17)Oδ(L1)·b(G1,δ)α≤b(G,δ)≤Oδ(L2)·b(G2,δ).Proof.
The same proof in Theorem3 applies by using Theorem 1.



---

*Source: 839846-2013-08-01.xml*