stochastic_mst_submodular_goal_value
The submodular goal value Q_ID(G) of a finite graph G is the infimum in ℕ (sInf) of the set of natural numbers Q such that there exists a submodular goal function g for G with goal value Q.
Statement
open scoped Classical in noncomputable def stochastic_mst_submodular_goal_value {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ
- Defined in
- scout/2610-40844-stochastic-minimum-spanning-tree-identification-with-binary.md:702
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 1
- is_submodular_goal_functionA function g : (G.edgeSet → Option Bool) → ℕ is a submodular goal function with goal value Q for G if: g evaluates to 0 on the empty…
- Used by 1
- tree_submodular_goal_value_zeroFor every finite simple graph G on a vertex type V that is a tree (G.IsTree), the submodular goal value…
Read back from the Lean
Given a finite type V and a simple graph G on V, stochastic_mst_submodular_goal_value G is defined as the infimum (in ℕ, which is the minimum if non-empty, and 0 if empty) of the set of natural numbers Q for which there exists a function g : (G.edgeSet → Option Bool) → ℕ such that g is a submodular goal function for G with goal value Q (is_submodular_goal_function G g Q).
A function g : (G.edgeSet → Option Bool) → ℕ is a submodular goal function for G with target value Q if:
1. g assigns 0 to the empty partial assignment (where every edge is none).
2. Monotonicity: For all partial assignments β, γ : G.edgeSet → Option Bool, if β ≤ γ (i.e., whenever β e = some b, then γ e = some b), then g β ≤ g γ.
3. Submodularity (diminishing returns): For all partial assignments β, γ : G.edgeSet → Option Bool, every edge e ∈ G.edgeSet, and every boolean s : Bool, if β ≤ γ and γ e = none, then
g (γ[e ↦ some s]) + g β ≤ g (β[e ↦ some s]) + g γ.
4. Goal condition: For all partial assignments β : G.edgeSet → Option Bool, g β = Q if and only if β is an MST certificate for G (is_mst_certificate G β).
Here, β is an MST certificate for G (is_mst_certificate G β) if there exists a subgraph T ≤ G such that:
- T is a tree (T.IsTree), and
- for every total edge assignment α : G.edgeSet → Bool extending β (i.e., α e = b whenever β e = some b), T is a minimum spanning tree for G under α (is_mst_for G T α), meaning that for every tree subgraph T' ≤ G, the sum of weights (1 if α e = true, 0 if α e = false) of edges in T is less than or equal to the sum of weights of edges in T'.
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
open scoped Classical in /-- The minimum goal value Q of a submodular goal function for G. -/ noncomputable def stochastic_mst_submodular_goal_value {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ := sInf {Q : ℕ | ∃ g, is_submodular_goal_function G g Q}