For any connected graph, the blanket and cover times are within an O(1) factor

You need to know: Graph, finite graph, connected graph, notation $G=(V,E)$ for graph with vertex set V and edge set E, notation $|E|$ for the number of edges in G, degree $\text{deg}(v)$ of vertex $v\in V$ , probability, selection uniformly at random, expectation, $O(1)$ notation.

Background: Let $G=(V,E)$ be a connected graph. A simple random walk on G is the process which starts at some vertex v at time $t=0$ , and then at times $t=1,2,\dots$ moves to an adjacent vertex selected uniformly at random. Let $\tau_\text{cov}$ be the first time at which every vertex of G has been visited, and let ${\mathbb E}_v[\tau_\text{cov}]$ be the expectation of $\tau_\text{cov}$ (which depend on the initial vertex v). Number $t_\text{cov}(G) = \max\limits_{v \in V}{\mathbb E}_v[\tau_\text{cov}]$ is called the cover time of G.

For any $v\in V$ , let $N_v(t)$ be a (random) number of times the random walk has visited v up to time t. For $\delta\in(0,1)$ , let $\tau_{\text{bl}}(\delta)$ be the first time $t\geq 1$ at which $N_v(t) \geq \delta t \frac{\text{deg}(v)}{2|E|}$ holds for all $v\in V$ . Number $t_\text{bl}(G,\delta) = \max\limits_{v \in V}{\mathbb E}_v[\tau_{\text{bl}}(\delta)]$ is called the $\delta$ –blanket time of G.

The Theorem: On 25th April 2010, Jian Ding, James Lee, and Yuval Peres submitted to arxiv a paper in which they proved that for every $\delta\in(0,1)$ , there exists a $C=C(\delta)$ such that for every connected graph G, one has $t_\text{bl}(G,\delta) \leq C t_\text{cov}(G)$ .

Short context: It is known that as $t\to\infty$ , the proportion of time a random walk spend at any vertex v converges to $\frac{\text{deg}(v)}{2|E|}$ . Hence, $\tau_{\text{bl}}(\delta)$ is the first time at which all nodes have been visited at least a $\delta$ fraction as much as we expect. Because $t_\text{cov}(G) \leq t_\text{bl}(G,\delta)$ by definition, the Theorem states that the blanket and cover times are within an O(1) factor. It confirms conjecture of Winkler and Zuckerman made in 1996.