Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The cube helper graphs QjQ_jQj​, cube-first coverage, and the binomial sum of (17)

Definition
CoverTime537_SpecifiedStart_Supplement_CubeHelper

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

computational-complexitymarkov-chainp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let G′G'G′ be the published hub graph of a source (the subdivided graph SSS with N=∣V(S)∣N=|V(S)|N=∣V(S)∣ vertices plus a universal hub zzz). For j∈Nj\in\mathbb Nj∈N, the graph QjQ_jQj​ adds

  1. eight cube vertices indexed by three-bit strings, two of them adjacent exactly when they differ in one bit, each also adjacent to zzz;
  2. jjj leaves, each adjacent to zzz only.

No other edges are added. The paper uses QjQ_jQj​ for j≥Nj\ge Nj≥N: the first NNN leaves are the permanent markers and the other j−Nj-Nj−N the probes. Thus ∣V(Qj)∣=N+9+j|V(Q_j)|=N+9+j∣V(Qj​)∣=N+9+j and ∣E(Qj)∣=∣E(G′)∣+20+j|E(Q_j)|=|E(G')|+20+j∣E(Qj​)∣=∣E(G′)∣+20+j.

For a start xxx, the cube-first probability is the probability that the ordinary walk on QjQ_jQj​ from xxx visits all eight cube vertices strictly before its first visit to zzz. It is the sum over ttt of the probabilities of the disjoint events "the cube is first fully covered at time ttt and zzz is not visited at times 0,…,t0,\dots,t0,…,t".

On the base graph QNQ_NQN​, with D=deg⁡QN(z)=2N+8D=\deg_{Q_N}(z)=2N+8D=degQN​​(z)=2N+8, write rsr_srs​ for the number of departures from the hub completed by time sss, i.e. the number of 0≤i<s0\le i<s0≤i<s with Xi=zX_i=zXi​=z. For k≥2k\ge2k≥2 and x=D+kx=D+kx=D+k, the summand of (17) along a walk prefix X0,…,XsX_0,\dots,X_sX0​,…,Xs​ is

(Dx)rs−2kx−1 1{Xs=z}(Dx−1)rs,\Big(\frac{D}{x}\Big)^{r_s}-\frac{2k}{x-1}\,\mathbf 1\{X_s=z\}\Big(\frac{D}{x-1}\Big)^{r_s},(xD​)rs​−x−12k​1{Xs​=z}(x−1D​)rs​,

and its expectation restricted to s≥τs\ge\taus≥τ (τ\tauτ the cover time of QNQ_NQN​) is the sum over walk prefixes that start at the chosen cube vertex and cover all of QNQ_NQN​, weighted by their path probabilities. Finally

BinomialSum(k)=∑j=0k(−1)j+1(kj)M(QN+j).\mathrm{BinomialSum}(k)=\sum_{j=0}^{k}(-1)^{j+1}\binom{k}{j}M(Q_{N+j}).BinomialSum(k)=j=0∑k​(−1)j+1(jk​)M(QN+j​).

These objects state Lemmas 10 and 11, the two labelled steps of the proof of Theorem 2.

Formalization Note The graph is the symmetric closure of the listed adjacencies; the hub is the published hub vertex none of G′G'G′. An absolute-value version of the time-sss term is also defined so that absolute summability can be stated.

Definition code
import Mathlib
import Definitions.Def_CoverTime537_SpecifiedStart_Construction
import Definitions.Def_CoverTime537_SpecifiedStart_Supplement_MaxCover

namespace CoverTime537.SpecifiedStart.Supplement
noncomputable section
open scoped BigOperators
open CoverTime537.SpecifiedStart

/-- Vertices of `Q_j` (§7, pp.13–14): the vertices of `G′ = hubGraph D`
(hub `none`), eight cube vertices indexed by three-bit strings, and `j` leaves.
Leaves `0, …, N−1` are the permanent markers, the rest the probes. -/
abbrev QVertex (D : Source) (j : ℕ) := HVertex D ⊕ ((Fin 3 → Bool) ⊕ Fin j)

instance (D : Source) (j : ℕ) : Nonempty (QVertex D j) := ⟨.inl none⟩

/-- Decidable equality assembled from the components (direct synthesis on the
nested sum exceeds the default instance-search budget). -/
instance (D : Source) (j : ℕ) : DecidableEq (QVertex D j) :=
  haveI : DecidableEq (HVertex D) := inferInstance
  haveI : DecidableEq ((Fin 3 → Bool) ⊕ Fin j) := inferInstance
  inferInstance

def hub (D : Source) (j : ℕ) : QVertex D j := .inl none
def cubeV (D : Source) (j : ℕ) (a : Fin 3 → Bool) : QVertex D j := .inr (.inl a)
def leaf (D : Source) (j : ℕ) (i : Fin j) : QVertex D j := .inr (.inr i)

def IsCube {D : Source} {j : ℕ} (x : QVertex D j) : Prop := ∃ a, x = cubeV D j a

/-- Generating relation: edges of `G′`; cube edges between strings differing in
exactly one bit; hub to every cube vertex and every leaf. Nothing else. -/
def qRel (D : Source) (j : ℕ) : QVertex D j → QVertex D j → Prop
  | .inl x, .inl y => (hubGraph D).Adj x y
  | .inl none, .inr _ => True
  | .inr (.inl a), .inr (.inl b) =>
      (Finset.univ.filter (fun i : Fin 3 => a i ≠ b i)).card = 1
  | _, _ => False

/-- The graph `Q_j`: the symmetric irreflexive closure of `qRel`. -/
def Q (D : Source) (j : ℕ) : SimpleGraph (QVertex D j) := SimpleGraph.fromRel (qRel D j)

/-- Probability, for the ordinary walk on `Q_j` from `x`, that the eight cube
vertices are all visited strictly before the first visit to the hub: disjoint
finite cylinders indexed by the time `t` at which cube coverage first occurs
(no hub visit at times `0..t`, every cube vertex seen by `t`, the vertex at `t`
not seen before). -/
def cubeFirstAt (D : Source) (j : ℕ) (x : QVertex D j) (t : ℕ) : ℝ := by
  classical
  exact ∑ w : Fin (t + 1) → QVertex D j,
    if w 0 = x ∧ (∀ i, w i ≠ hub D j) ∧ (∀ a, ∃ i, w i = cubeV D j a) ∧
      (∀ i : Fin (t + 1), i.val < t → w i ≠ w (Fin.last t))
    then MarkovMixing.pathWeight (walk (Q D j)) w else 0

def cubeFirstProb (D : Source) (j : ℕ) (x : QVertex D j) : ℝ :=
  ∑' t, cubeFirstAt D j x t

/-- §8, p.16: `D = deg_{Q_N}(z) = 2N + 8` (N subdivided vertices, eight cube
vertices and N markers). -/
def hubDeg (D : Source) : ℕ := 2 * N D + 8

/-- Departures from the hub completed by time `s`: indices `0 ≤ i < s` with
`X_i = z` (a step out of the hub; returns to it are not counted). -/
def departures {D : Source} {j s : ℕ} (w : Fin (s + 1) → QVertex D j) : ℕ := by
  classical
  exact (Finset.univ.filter (fun i : Fin (s + 1) => i.val < s ∧ w i = hub D j)).card

/-- The summand of (17) at time `s` along a prefix `w`, with `x = D + k`:
`(D/x)^{r_s} − (2k/(x−1))·1{X_s = z}·(D/(x−1))^{r_s}`. -/
def term11 (D : Source) (k : ℕ) {s : ℕ} (w : Fin (s + 1) → QVertex D (N D)) : ℝ :=
  let x : ℝ := (hubDeg D : ℝ) + k
  ((hubDeg D : ℝ) / x) ^ departures w -
    (2 * (k : ℝ) / (x - 1)) * (if w (Fin.last s) = hub D (N D) then 1 else 0) *
      ((hubDeg D : ℝ) / (x - 1)) ^ departures w

/-- `E_c[ g_s · 1{s ≥ τ} ]` for the base walk on `Q_N` from `c`, with `g = term11`
(or its absolute value): `s ≥ τ` iff the prefix `X_0, …, X_s` covers `Q_N`. -/
def lemma11At (D : Source) (k : ℕ) (c : QVertex D (N D)) (abs : Bool) (s : ℕ) : ℝ := by
  classical
  exact ∑ w : Fin (s + 1) → QVertex D (N D),
    if w 0 = c ∧ (∀ v, ∃ i, w i = v) then
      MarkovMixing.pathWeight (walk (Q D (N D))) w *
        (if abs then |term11 D k w| else term11 D k w)
    else 0

/-- `BinomialSum(k) = Σ_{j=0}^{k} (−1)^{j+1} C(k,j) M(Q_{N+j})`, eq. (17). -/
def binomialSum (D : Source) (k : ℕ) : ℝ :=
  ∑ j ∈ Finset.range (k + 1),
    (-1 : ℝ) ^ (j + 1) * (Nat.choose k j : ℝ) * maxCover (Q D (N D + j))

end
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, §7 pp.13–14 (construction of Q_j, Figure 3), Lemma 10 p.14, §8 p.16 (D, X_s, τ, r_s, eq. (17))

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me