is_submodular_goal_function
A 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 assignment (fun _ => none); g is monotone under partial assignment extension (partial_assignment_le β γ → g β ≤ g γ); g satisfies state-dependent submodularity (for all β ≼ γ and e with γ e = none, g(γ_{e ← s}) + g(β) ≤ g(β_{e ← s}) + g(γ)); and g(β) = Q if and only if β is an MST identification certificate for G (is_mst_certificate G β).
Statement
open scoped Classical in def is_submodular_goal_function {V : Type*} [Fintype V] (G : SimpleGraph V) (g : (G.edgeSet → Option Bool) → ℕ) (Q : ℕ) : Prop
- Defined in
- scout/2610-40844-stochastic-minimum-spanning-tree-identification-with-binary.md:686
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 2
- partial_assignment_leA partial assignment β is extended by γ (written β ≼ γ) if for every element e and boolean value b, β(e) = some b implies γ(e) = some b.
- is_mst_certificateA partial realization β : G.edgeSet → Option Bool is an MST identification certificate for G if there exists a spanning tree T of G (T ≤ G…
- Used by 2
- stochastic_mst_submodular_goal_valueThe 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…
- 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
For a finite vertex type V, a simple graph G on V, a function g : (G.edgeSet → Option Bool) → ℕ, and a natural number Q, is_submodular_goal_function G g Q asserts the conjunction of four properties:
1. (Base value) g maps the completely unassigned partial assignment (the constant none function) to 0.
2. (Monotonicity) For all partial assignments β and γ, if β ≤ γ (i.e., for every edge e and boolean b, if β(e) = some b then γ(e) = some b), then g(β) ≤ g(γ).
3. (Submodularity / Diminishing returns) For all partial assignments β and γ, every edge e ∈ G.edgeSet, and every boolean s, if β ≤ γ and γ(e) = none, then
g(γ[e ↦ some s]) + g(β) ≤ g(β[e ↦ some s]) + g(γ).
4. (Target characterization) For all partial assignments β, g(β) = Q if and only if β is an MST certificate for G (is_mst_certificate G β).
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 /-- A submodular goal function with goal value Q for stochastic MST identification. -/ def is_submodular_goal_function {V : Type*} [Fintype V] (G : SimpleGraph V) (g : (G.edgeSet → Option Bool) → ℕ) (Q : ℕ) : Prop := g (fun _ => none) = 0 ∧ (∀ β γ, partial_assignment_le β γ → g β ≤ g γ) ∧ (∀ β γ e s, partial_assignment_le β γ → γ e = none → g (Function.update γ e (some s)) + g β ≤ g (Function.update β e (some s)) + g γ) ∧ (∀ β, g β = Q ↔ is_mst_certificate G β)