AFTD Auto-Formalizing Theoretical Domains

nonadaptive_mst_stopping_time

def

Given a simple graph G, a querying order π : List G.edgeSet, and a realization α : G.edgeSet → Bool, the stopping time is the minimum number of queries k such that the partial realization revealing the first k edges of π certifies an MST of G.

Statement

noncomputable def nonadaptive_mst_stopping_time {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (π : List G.edgeSet) (α : G.edgeSet → Bool) : ℕ
Defined in
arXiv:2610.40844 Sec. 2.1, Lemma 2.2
Verified
07 Nov 2026
Axioms
none listed
Built on 1
  • is_mst_certificateA partial realization β : G.edgeSet → Option Bool is an MST identification certificate for G if there exists a spanning tree T of G (T ≤ G…
Used by 2
  • nonadaptive_mst_stopping_time_of_isTreeIf G is a tree, then under any binary edge realization α and any querying order π, the stopping time is 0 because the unique spanning tree…
  • nonadaptive_mst_expected_costThe expected query cost of a non-adaptive querying order π on a finite graph G with decidable adjacency and edge probabilities p is the…

Read back from the Lean

Given a finite type V with decidable equality, a simple graph G on V, a list π of edges of G, and a boolean edge-weight assignment α : G.edgeSet → Bool, nonadaptive_mst_stopping_time G π α is defined as the infimum (in ℕ, via sInf) of the set of natural numbers k such that the partial function revealing the values of α on the first k edges of π (and none elsewhere) forms an MST certificate for G (is_mst_certificate).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The number of queries performed by querying edges in order π until an MST is certified under realization α. -/
noncomputable def nonadaptive_mst_stopping_time {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (π : List G.edgeSet) (α : G.edgeSet → Bool) : ℕ := sInf {k : ℕ | is_mst_certificate G (fun e => if e ∈ (π.take k).toFinset then some (α e) else none)}
See it in the graphDiscuss this resultChallenge it