Exponential upper bound for linear-time graph covering

Definitions and mathematical statement

Let $G$ be a finite simple graph with $n$ vertices and let $(X_t)_{t\geq0}$ be discrete-time simple random walk, choosing a uniformly random neighbor at each step. For a specified starting vertex $v$, define \[ T_{\mathrm{cov}}=\inf\{t\geq0:\{X_0,\ldots,X_t\}=V(G)\}. \] The literal conjecture asks: for each finite time factor $C$, is there $c=c(C)<1$, independent of $G,n$, such that \[ \Pr_v(T_{\mathrm{cov}}\leq\lfloor Cn\rfloor)\leq c^n \] for every simple graph? A natural probability-bound interpretation requires $C>0$ and $0<c<1$, with the starting convention fixed.

There is a finite-size discrepancy in the printed all-$n$ statement. For the one-vertex graph the usual cover time is zero, so the probability is one. Also, on the two-vertex edge the cover time from either vertex is deterministically one. For time factors allowing that step, no bound by $c^2<1$ holds. Thus a nontrivial intended formulation needs a sufficiently-large-$n$ qualification or a multiplicative prefactor.

One explicit asymptotic candidate is: for every $C>0$ there exist $c(C)\in(0,1)$ and $n_0(C)$ such that the display holds for all $n\geq n_0(C)$, all connected simple $n$-vertex graphs, and all starts $v$. Equivalently at the exponential scale one can ask for $A(C)e^{-a(C)n}$ with $a(C)>0$ and finite $A(C)$. These are identified repairs, not silently substituted source quantifiers. Disconnected graphs cannot be covered from one component, apart from trivial conventions; isolated vertices need a random-walk definition.

The graph class in the statement is arbitrary simple graphs, not only planar or bounded-degree graphs, and the question is a lower-tail probability bound rather than a bound on expected cover time.

Short English statement

Show that covering an arbitrary simple graph in only a fixed multiple of its vertex count has exponentially small probability. The literal all-size form needs a finite-size qualification, and the walk's starting convention is missing.

Sources

• Local UnsolvedMath registry, permanent ID 10000083, exact source code catalogue entry, "Exponential upper bound for linear-time graph covering"; attributed to Itai Benjamini, no proposed year supplied. Registry status open, classification OPEN-TRIAGE.
• Itai Benjamini, Random Planar Metrics, section 4.1 cover-time conjecture, PDF page 9, https://www.wisdom.weizmann.ac.il/~itai/randomplanar2.pdf#page=9, preserved at https://arquivo.pt/noFrame/replay/20201231041544id_/http://www.wisdom.weizmann.ac.il/~itai/randomplanar2.pdf. Supplied pypdf text checked against a rendered PDF, accessed July 29, 2026. No PDF/rendering was accessed here.
• The supplied summary reports no established exponential bound for this linear-time-cover question. Provenance records cross-document/source-side review and a bounded modern audit finding no complete primary resolution.
• Current status and release-reuse terms remain NEEDS_REVIEW.