AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_solves_aux

def

From state (Z, D) of contracted edges Z and deleted edges D, a strategy solves the adaptive MST identification problem for G if at every leaf no edge of G is query-eligible (all remaining edges of the minor are loops or bridges, certifying an MST), and each internal node queries an unqueried edge of G with its 0-child and 1-child solving the subproblems after contracting and deleting e, respectively.

Statement

def stochastic_mst_solves_aux {V : Type*} [DecidableEq V] (G : SimpleGraph V) (Z D : Finset (Sym2 V)) :
    StochasticMstStrategy (Sym2 V) → Prop
Defined in
arXiv:2610.40844 Sections 2.1 & 3
Verified
07 Nov 2026
Axioms
none listed
Built on 2
  • StochasticMstStrategyAn adaptive strategy for binary stochastic MST identification is a binary decision tree on a type of edges: either a leaf (no further…
  • 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 3
  • stochastic_mst_solvesA strategy T solves the adaptive MST identification problem for G if it solves the problem starting from the empty state of contracted and…
  • tutte_strategy_solves_stochastic_mstFor any graph G, every Tutte strategy T for G solves the adaptive MST identification problem for G.
  • stochastic_mst_query_continuation_solvesFor a graph G and an edge e that is query-eligible at the initial state (∅, ∅), the strategy querying e with children s₀ and s₁ solves the…

Read back from the Lean

Given a type V with decidable equality, a simple graph G on V, two finite sets Z, D : Finset (Sym2 V) of unordered pairs of vertices, and a decision tree strategy s : StochasticMstStrategy (Sym2 V), stochastic_mst_solves_aux G Z D s is a recursively defined proposition asserting that: 1. If s is StochasticMstStrategy.leaf: no edge e : Sym2 V is query-eligible with respect to G, Z, and D (i.e., ∀ e : Sym2 V, ¬ stochastic_mst_query_eligible G Z D e). 2. If s is StochasticMstStrategy.query e s₀ s₁: - e is an edge of G (e ∈ G.edgeSet), - e ∉ Z, - 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

/-- Predicate stating that a strategy solves the adaptive MST identification problem for G from state (Z, D). -/
def stochastic_mst_solves_aux {V : Type*} [DecidableEq V] (G : SimpleGraph V) (Z D : Finset (Sym2 V)) :
    StochasticMstStrategy (Sym2 V) → Prop
| StochasticMstStrategy.leaf => ∀ e, ¬ stochastic_mst_query_eligible G Z D e
| StochasticMstStrategy.query e s₀ s₁ =>
    e ∈ G.edgeSet ∧ e ∉ Z ∧ e ∉ D ∧
    stochastic_mst_solves_aux G (insert e Z) D s₀ ∧
    stochastic_mst_solves_aux G Z (insert e D) s₁
See it in the graphDiscuss this resultChallenge it