Lemma 10 — known maximizing starts of
OpenCoverTime537.SpecifiedStart.Supplement.lemma_10computational-complexitymarkov-chainp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability
Let be the hub graph of a source with , and for let be with the cube helper and hub leaves attached. There is one rational number with
such that for every source and every :
- a vertex of maximizes the expected cover time, i.e. for all , if and only if is one of the eight cube vertices;
- from each cube vertex, the probability that the walk on visits all eight cube vertices before its first visit to the hub is exactly .
In particular for any cube vertex , which is how the maximum-start oracle is used in the proof of Theorem 2.
Differences from the source:
- generalization: a fixed rational ρ ≥ 2^−14 independent of j (for the fixed source of the reduction) → one rational ρ ≥ 2^−14 chosen before every source and every j ≥ N; reason: the source's ρ comes from the walk inside the cube, whose transitions depend on neither j nor the source (p.15); fixing D gives the source's claim
- encoding: 'computable rational' → ρ : ℚ; reason: a fixed rational is computable; no algorithmic clause is needed
- encoding: probability of covering the cube before reaching the hub → sum over t of finite path-cylinder probabilities of first cube coverage at time t with no hub visit at times 0..t; reason: the events are disjoint and their union is the source's event
Preamble
import Definitions.Def_CoverTime537_SpecifiedStart_Supplement_CubeHelper
Formal statement
namespace CoverTime537.SpecifiedStart.Supplement
open CoverTime537.SpecifiedStart
/-- Aghazadeh, STOC 2027 submission #537, Lemma 10, p.14.
One rational `ρ ≥ 2^{-14}`, fixed before every source and every `j ≥ N`: the
maximizing starts of `Q_j` are exactly the eight cube vertices, and from each
cube vertex the cube is covered before the first hub visit with probability `ρ`. -/
theorem lemma_10 :
∃ ρ : ℚ, (2 : ℚ) ^ (-14 : ℤ) ≤ ρ ∧
∀ (D : Source) (j : ℕ), N D ≤ j →
(∀ x : QVertex D j,
(∀ y : QVertex D j, cover (Q D j) y ≤ cover (Q D j) x) ↔ IsCube x) ∧
∀ a : Fin 3 → Bool, cubeFirstProb D j (cubeV D j a) = (ρ : ℝ) := by sorry
end CoverTime537.SpecifiedStart.Supplement
Source
Ryan Aghazadeh, How Hard Is It to Compute Cover Time?, STOC 2027 submission #537 (October 2026), papers/stoc2027-537/source.pdf, SHA-256 4487efe2e616b5ed1b0e9a8a4172a4b53fd492c5d9ad4717ed4921b088564fd8, Lemma 10 p.14, proof pp.14–15; construction of Q_j §7 pp.13–14