Cover-time robustness can stay positive while hitting-time robustness vanishes: an explicit separation of two robustness notions for adversarial random walks

Unrefereed research candidate. A random walk explores a network by stepping to a uniformly chosen neighbour. The hitting time is the expected time to reach one given vertex; the cover time is the expected time to visit every vertex. Zuckerman (Markov Chain Robustness, ITCS 2026) asked how much an adversary who may change every transition probability by a relative factor in [1-ε, 1+ε], with history-dependent choices, can slow these down, and conjectured (Conjecture 1.17) that the tolerable ε for hitting time and for cover time always agree up to a constant factor. Result: the conjecture fails. Take a complete graph on N = 2^(2^L) vertices, attach a private leaf to every vertex, and attach one extra path of length L. For every fixed amplification budget C > 1, the hitting-time tolerance satisfies Lρ_hit → a_C, where (e^(2a_C)-1)/(2a_C) = C, because a small bias compounds along the path; but the cover-time tolerance tends to min{1-C^(-1/2), 1/3} > 0, because collecting the leaves dominates and is inflated only by (1-ε)^(-2). For C = 2 these are about 0.628/L and 0.293. The ratio grows like log log |V|. The manuscript also proves a uniform cover-response formula, the exact critical multiplier 9/4 + 9/(8 log 2) ≈ 3.873 and tolerance expansions through order 1/L. Scope: the graphs have unbounded degree and are astronomically large (an asymptotic theorem, not a statement about practical sizes); bounded-degree and regular versions, the converse direction and the strong-adversary cover tolerance remain open. Finite exact-rational and high-precision checks (verify_markov.py, verify_critical.py) are supplementary and do not establish the asymptotic claims. A sibling candidate (DOI 10.5281/zenodo.23575572) answers the different Conjecture 1.16 on diameter and hitting time. Archive: manuscript (Markdown source and PDF), figure, verification scripts and their JSON outputs, novelty report and addendum, bibliography with registry records, CI and SHA-256 manifest. Assurance: internal AI-assisted review only (not human peer review, independent reproduction or formal verification). Creator: Anonymous. Text CC0-1.0; code MIT.