AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_priority_cost_aux

def

For a simple graph G on a finite vertex type V with decidable adjacency, p : Sym2 V → ℝ and a list pi of edges (List (Sym2 V)), the expected number of further queries of the priority strategy for pi from the state (Z, D) of finite edge sets (Finsets of Sym2 V), with fuel k : ℕ: it is 0 when k = 0, and also 0 when no element of pi satisfies stochastic_mst_query_eligible G Z D; otherwise, for e the first element of pi (List.find?) with stochastic_mst_query_eligible G Z D e, it is 1 + p e * value(k-1, Z, insert e D) + (1 - p e) * value(k-1, insert e Z, D).

Statement

noncomputable def stochastic_mst_priority_cost_aux {V : Type*} [Fintype V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (p : Sym2 V → ℝ) (π : List (Sym2 V)) :
    ℕ → Finset (Sym2 V) → Finset (Sym2 V) → ℝ
Defined in
arXiv:2610.40844 (Stochastic Minimum Spanning Tree Identification with Binary Weights), Sec. 3, ExecuteTutteStrategy(pi): query edges in the order pi, skipping those that are loops or bridges of the current minor
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • stochastic_mst_query_eligibleFor a simple graph G on a vertex type V, finite sets Z and D of edges (Finsets of Sym2 V: Z the edges queried with weight 0, which are…
Used by 2

Read back from the Lean

stochastic_mst_priority_cost_aux defines a function taking: - a type V with a Fintype V instance, - a simple graph G on V with a DecidableRel G.Adj instance, - a function p : Sym2 V → ℝ, - a list π : List (Sym2 V), - a natural number k : ℕ (recursion depth), - two finite sets of unordered pairs of vertices Z, D : Finset (Sym2 V), and returning a real number ℝ. It is defined by recursion on k: - If k = 0, it returns 0 (for any Z and D). - If k + 1, it searches the list π for the first element e such that stochastic_mst_query_eligible G Z D e holds (using classical decidability): - If no such element exists in π, it returns 0. - If such an element e is found, it returns: 1 + p e * stochastic_mst_priority_cost_aux G p π k Z (insert e D) + (1 - p e) * stochastic_mst_priority_cost_aux G p π k (insert e Z) D.

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_priority_cost_aux {V : Type*} [Fintype V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (p : Sym2 V → ℝ) (π : List (Sym2 V)) :
    ℕ → Finset (Sym2 V) → Finset (Sym2 V) → ℝ := fun
  | 0, _, _ => 0
  | k + 1, Z, D =>
    open Classical in
    match π.find? (fun e => decide (stochastic_mst_query_eligible G Z D e)) with
    | none => 0
    | some e => 1 + p e * stochastic_mst_priority_cost_aux G p π k Z (insert e D)
        + (1 - p e) * stochastic_mst_priority_cost_aux G p π k (insert e Z) D
See it in the graphDiscuss this resultChallenge it