The probability that the random walk in a bounded degree planar graph avoids its initial location for T steps is at most C/log T

You need to know: Graph, finite graph, planar graph, degree of a vertex in a graph, probability, selection uniformly at random.

Background: A simple random walk on graph G is the process which starts at some vertex $v_0$ at time $t=0$ , and then at times $t=1,2,\dots$ moves to an adjacent vertex selected uniformly at random. Assuming that initial vertex $v_0$ is selected uniformly at random from vertices of G, denote $\phi(T,G)$ the probability that the walk does not return to $v_0$ for T steps. Let ${\cal G}(D)$ be the set of all finite planar graphs with degrees of all vertices bounded by D, and let $\phi_D(T)=\sup\limits_{G \in {\cal G}(D)} \phi(T,G)$ .

The Theorem: On 4th June 2012, Ori Gurel-Gurevich and Asaf Nachmias submitted to arxiv and the Annals of Mathematics a paper in which they proved that for any $D\geq 1$ , there exists a constant $C=C(D)<\infty$ such that $\phi_D(T) \leq \frac{C}{\log T}$ for any $T \geq 2$ .

Short context: The study of random walks on graphs is one of the central research directions in probability theory with numerous applications, and walks on bounded-degree planar graphs form an important special case. In 2001, Benjamini and Schramm proved that $\phi_D(T) \to 0$ as $T\to\infty$ , but left the rate of decay of $\phi_D(T)$ as an open question. Because it is known that $\phi_D(T) \geq \frac{c}{\log T}$ for some constant $c>0$ , the Theorem answers this question up to a constant factor.