AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_adaptive_cost

def

For a simple graph G on a finite vertex type V with decidable adjacency and p : Sym2 V → ℝ, A(G,p) := stochastic_mst_adaptive_cost_aux G p applied with fuel G.edgeFinset.card (the number of edges of G) to the empty state Z = ∅, D = ∅: the minimum expected number of edge queries of an adaptive strategy certifying a minimum spanning tree.

Statement

noncomputable def stochastic_mst_adaptive_cost {V : Type*} [Fintype V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (p : Sym2 V → ℝ) : ℝ
Defined in
arXiv:2610.40844 (Stochastic Minimum Spanning Tree Identification with Binary Weights), Sec. 2-3: the adaptive Stochastic MST-ID problem
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • stochastic_mst_adaptive_cost_auxFor a simple graph G on a finite vertex type V with decidable adjacency and p : Sym2 V → ℝ (p e the probability that edge e has weight 1),…
Used by 1

Read back from the Lean

stochastic_mst_adaptive_cost defines a real number for a finite type V, a simple graph G on V with decidable adjacency, and a function p : Sym2 V → ℝ. It is defined as stochastic_mst_adaptive_cost_aux G p G.edgeFinset.card ∅ ∅, which computes the optimal expected cost of an adaptive query process using at most |E(G)| steps, starting with empty sets of resolved edges Z = ∅ and D = ∅. Specifically, stochastic_mst_adaptive_cost_aux G p k Z D is defined recursively on k : ℕ: - If k = 0, it returns 0. - If k + 1, it checks whether the set of edges e ∈ G.edgeFinset satisfying stochastic_mst_query_eligible G Z D e is nonempty: - If nonempty, it takes the infimum (minimum) over all eligible edges e of: 1 + p(e) * aux(k, Z, D ∪ {e}) + (1 - p(e)) * aux(k, Z ∪ {e}, D). - If empty, it returns 0. An edge e : Sym2 V is stochastic_mst_query_eligible G Z D e if: 1. e ∈ G.edgeSet, 2. e ∉ Z, 3. e ∉ D, and 4. There exist u, v : V such that e = s(u, v), u and v are not reachable from each other in the graph whose edge set is Z, and u and v are reachable from each other in the graph obtained from G by deleting D ∪ {e}.

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

noncomputable def stochastic_mst_adaptive_cost {V : Type*} [Fintype V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (p : Sym2 V → ℝ) : ℝ :=
  stochastic_mst_adaptive_cost_aux G p G.edgeFinset.card ∅ ∅
See it in the graphDiscuss this resultChallenge it