stochastic_mst_is_tutte_aux
From state (Z, D) of contracted edges Z and deleted edges D, a strategy is a Tutte strategy for G if at a leaf no edge of G is query-eligible (every remaining edge of the minor is a loop or bridge), and at an internal query on e, e is query-eligible at (Z, D), the 0-child is a Tutte strategy from (insert e Z, D), and the 1-child is a Tutte strategy from (Z, insert e D).
Statement
def stochastic_mst_is_tutte_aux {V : Type*} [DecidableEq V] (G : SimpleGraph V) (Z D : Finset (Sym2 V)) : StochasticMstStrategy (Sym2 V) → Prop
- Defined in
- arXiv:2610.40844 Section 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 2
- tutte_strategy_solves_stochastic_mstFor any graph G, every Tutte strategy T for G solves the adaptive MST identification problem for G.
- stochastic_mst_is_tutteA strategy T is a Tutte strategy for G if it satisfies the Tutte strategy predicate starting from the empty state of contracted and…
Read back from the Lean
A recursive predicate on strategy trees s : StochasticMstStrategy (Sym2 V), parameterized by a type V with decidable equality, a simple graph G on V, and two finite sets of undirected edges Z, D : Finset (Sym2 V).
Defined by pattern matching on s:
1. If s is a leaf (StochasticMstStrategy.leaf), it asserts that no edge e : Sym2 V is query-eligible with respect to (G, Z, D) (i.e., ∀ e, ¬ stochastic_mst_query_eligible G Z D e).
2. If s is an internal query node (StochasticMstStrategy.query e s₀ s₁), it asserts the conjunction of:
- e is query-eligible with respect to (G, Z, D) (stochastic_mst_query_eligible G Z D e),
- the predicate holds recursively for subtree s₀ with Z updated to insert e Z and D unchanged (stochastic_mst_is_tutte_aux G (insert e Z) D s₀), and
- the predicate holds recursively for subtree s₁ with Z unchanged and D updated to insert e D (stochastic_mst_is_tutte_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 is a Tutte strategy from state (Z, D) of contracted and deleted edges. -/ def stochastic_mst_is_tutte_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₁ => stochastic_mst_query_eligible G Z D e ∧ stochastic_mst_is_tutte_aux G (insert e Z) D s₀ ∧ stochastic_mst_is_tutte_aux G Z (insert e D) s₁