Sandwich Theorem of Cover Times

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. 1. Introduction Let be a connected graph with vertices and edges. Consider a simple random walk on : we start at a vertex ; if at step we are at vertex , then we move from to a neighbor at step with probability , where is the degree of . Let be the expectation operator governing the random walk started at vertex . The cover time of is defined as where is the first time that all vertices of have been traversed [1]. Another relevant quantity is the strong -blanket time [2]. For , let be the stationary measure of the random walk, and let be the number of visits to up to time . For , the strong -blanket time is defined as where is the first time such that holds for any two vertices and . Clearly, we have for any . 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 functional from Talagrand’s theory of majorizing measures [5, 6]; see Theorem 1. We first review the functional in brief. Consider a compact metric space , and let , for . For a partition of and an element , denote by the unique set containing . An admissible sequence of partitions of is that is a refinement of , and for . The functional is defined as where represents the diameter of , that is, . Throughout the paper, we view graph as a metric space with distance induced by the commute time between two vertices . Hence, is a compact metric space. Theorem 1 (see [4]). For any graph and , where means for some constants , and furthermore, emphasizes that the constants may depend on . Here, . A comparison theorem for cover times is also presented. Theorem 2 (see [4]). Suppose that graphs and are on the same vertex set , and and are the distances induced by respective commute times. If there exists a number such that for all , then 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 graphs , , and are on the same vertex set and that , , and are the distances induced by respective commute times. If there exist , , and such that for all , then Proof. From the assumption, we have for all vertices and . Capitalizing on the -inequality, which says that where if and if , we obtain by using definition (4). It follows from Theorem 1 that as desired. Generally, the conditions imposed on commute times in