AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_solves

def

A strategy T solves the adaptive MST identification problem for G if it solves the problem starting from the empty state of contracted and deleted edges.

Statement

def stochastic_mst_solves {V : Type*} [DecidableEq V] (G : SimpleGraph V)
    (T : StochasticMstStrategy (Sym2 V)) : Prop
Defined in
arXiv:2610.40844 Sections 2.1 & 3
Verified
07 Nov 2026
Axioms
none listed
Built on 2
  • stochastic_mst_solves_auxFrom state (Z, D) of contracted edges Z and deleted edges D, a strategy solves the adaptive MST identification problem for G if at every…
  • StochasticMstStrategyAn adaptive strategy for binary stochastic MST identification is a binary decision tree on a type of edges: either a leaf (no further…
Used by 3

Read back from the Lean

Given a type V with decidable equality, a simple graph G on V, and a decision tree T : StochasticMstStrategy (Sym2 V), stochastic_mst_solves G T asserts that T is a valid decision tree solving the stochastic minimum spanning tree (MST) edge-classification process on G, starting with empty sets of contracted/retained edges Z = ∅ and deleted/discarded edges D = ∅. Specifically, stochastic_mst_solves G T holds if and only if stochastic_mst_solves_aux G ∅ ∅ T holds, where for any finite edge sets Z, D : Finset (Sym2 V): 1. If T = StochasticMstStrategy.leaf, then no edge e : Sym2 V is query-eligible with respect to G, Z, and D (i.e., ∀ e, ¬ stochastic_mst_query_eligible G Z D e). 2. If T = StochasticMstStrategy.query e s₀ s₁, then: - e is an edge of G (e ∈ G.edgeSet), - e is not currently in Z (e ∉ Z), - e is not currently in D (e ∉ D), - the left subtree s₀ satisfies stochastic_mst_solves_aux G (insert e Z) D s₀, and - the right subtree s₁ satisfies stochastic_mst_solves_aux G Z (insert e D) s₁.

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

/-- A strategy solves the adaptive MST identification problem for G if it solves it starting from (∅, ∅). -/
def stochastic_mst_solves {V : Type*} [DecidableEq V] (G : SimpleGraph V)
    (T : StochasticMstStrategy (Sym2 V)) : Prop := stochastic_mst_solves_aux G ∅ ∅ T
See it in the graphDiscuss this resultChallenge it