20 problems

Let $G$ be a finite graph with vertex set $V$. For a starting vertex $v\in V$, write $\mathbb{E}_v$ for expectation for the simple random walk started at $v$, and let the…

Let $G=(V,E)$ be a finite connected planar graph with $n$ vertices and maximal degree $M$. For every vertex $v\in V$, let ${\mathbf E}_v C$ denote the expected cover time of a rand…

Let the competitive random walk (CRW) run on the $\sqrt{n} \times \sqrt{n}$ grid, with a controller choosing at each step the less frequently visited of the two sampled vertices. A…

Boundary-condition conjecture. Similar results to Theorems and should hold for these alternative boundary conditions, in particular yielding corresponding asymptotics and limiting…

Let $D$ be an admissible domain and let $D_N$ be its lattice approximation, with returns made through the boundary vertex $\varrho$. Let $\tau_{\operatorname{cov}}$ denote the cove…

Cover-time conjecture. Almost surely,

Let $\mathcal{T}$ be the Brownian continuum random tree, let $\tau_{\mathrm{cov}}^{+}(\mathcal{T})$ denote the first time Brownian motion on $\mathcal{T}$ returns to its starting p…

Let ${\mathbf T}^{\mathbf C}_N$ be the cover time of the wired planar domain considered above, and let ${\mathbf t}^{\mathbf C}_N$ be defined by … For the corresponding random walk…

Let $G=(V,E)$) be a finite connected vertex-transitive graph. Write $P$ for the transition matrix of simple random walk on $G$, let $ut:=minvsum{i=0}^{t}P^i(v,v)$, and define … Le…

Let $G=(V,E)$ be a connected graph with $n=|V|$ vertices and degrees $d(u)$. Give each edge $(u,v)$ the conductance … The resulting random walk has cover time … This conjecture ass…

Polynomial wakeup-time conjecture. The wakeup time is conjectured to be polynomial in $n$.

Let $K_F$ be the graph under consideration, let $\ell_e$ denote the length of the subdivided path corresponding to an edge $e$ of $K_F$, and let $\ell^*$ be the threshold in the co…

Let $G(n,p)$ be the binomial random graph with $p=(1+\varepsilon)/n$, where $\varepsilon=o(1)$ and $\varepsilon^3n\to\infty$. Write $\mathcal{C}_1$ for its largest component and…

Let $G$ be a rooted graph on $n$ vertices, with root $r$, and let $cc_r(G)$ and $CT_r(G)$ denote its cover cost and cover time from $r$. The path on $n$ vertices rooted at an endpo…

Let $G_w$ be a graph equipped with the minimum-degree weighting scheme, let $n$ be its number of vertices, and let $d$ be the parameter used in the locally tree-like analysis. Let…

Let $G=(V,E)$) be a graph. For a random walk on $G$, let $\text{{\bf COV}}[G]$ denote its cover time and let $\text{{\bf BCOV}}[G]$ denote the blanket-cover time, the expected firs…

Let $G_N=(V,E)$ be a finite, connected planar graph with $N$ vertices and maximal degree $d$, and let $\tau(G_N)$ denote its cover time. The cover-time conjecture states that … whe…

Degree-independent cover-time conjecture. The same conclusion holds with $\alpha=\alpha(C)>0$ independent of the maximum degree $D$ whenever $G$ is simple:

Let $G$ be a graph on $n$ vertices, let $k$ satisfy $n\geq k\geq 1$, and write $S^k(G)$ for the speed-up in covering the graph. Logarithmic speed-up conjecture. For any graph $G$ a…

Let $G$ be a graph, let $k\geq 1$ be the number of random walks, and write $S^k(G)$ for their speed-up in covering the graph. Linear speed-up conjecture. For any graph $G$ and any…