AFTD Auto-Formalizing Theoretical Domains

stochastic_mst_adaptive_cost_le_priority_cost

theoremverified

For every finite simple graph G and every p with 0 <= p_e <= 1 on the edges, A(G,p) <= P(G,p): every fixed-priority strategy is an adaptive Tutte strategy, so the optimal adaptive cost is at most its cost.

Statement

theorem stochastic_mst_adaptive_cost_le_priority_cost {V : Type*} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (p : Sym2 V → ℝ)
    (hp : ∀ e ∈ G.edgeSet, 0 ≤ p e ∧ p e ≤ 1) :
    stochastic_mst_adaptive_cost G p ≤ stochastic_mst_priority_cost G p
Source
The easy inequality behind OP-1209 (arXiv:2610.40844 (Stochastic Minimum Spanning Tree Identification with Binary Weights), Sec. 3): fixed-priority strategies are among the adaptive ones
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • stochastic_mst_priority_costFor a simple graph G on a finite vertex type V with decidable adjacency and p : Sym2 V → ℝ, P(G,p) is the infimum (sInf in ℝ) of the set…
  • stochastic_mst_adaptive_costFor a simple graph G on a finite vertex type V with decidable adjacency and p : Sym2 V → ℝ, A(G,p) := stochastic_mst_adaptive_cost_aux G p…
  • stochastic_mst_priority_cost_auxFor a simple graph G on a finite vertex type V with decidable adjacency, p : Sym2 V → ℝ and a list pi of edges (List (Sym2 V)), the…
  • 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…
  • stochastic_mst_adaptive_cost_auxFor a simple graph G on a finite vertex type V with decidable adjacency and p : Sym2 V → ℝ (p e the probability that edge e has weight 1),…

Lean source view module on GitHub

theorem stochastic_mst_adaptive_cost_aux_le_priority_cost_aux {V : Type*} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (p : Sym2 V → ℝ)
    (hp : ∀ e ∈ G.edgeSet, 0 ≤ p e ∧ p e ≤ 1) (π : List (Sym2 V))
    (hπ : ∀ e ∈ G.edgeFinset, e ∈ π) (k : ℕ) :
    ∀ Z D, stochastic_mst_adaptive_cost_aux G p k Z D ≤
      stochastic_mst_priority_cost_aux G p π k Z D := by
  induction k with
  | zero => intro Z D; exact le_refl _
  | succ k ih =>
    intro Z D
    classical
    simp only [stochastic_mst_adaptive_cost_aux, stochastic_mst_priority_cost_aux]
    have key : ∀ e, List.find? (fun e => decide (stochastic_mst_query_eligible G Z D e)) π = some e →
        e ∈ G.edgeFinset.filter (fun e => stochastic_mst_query_eligible G Z D e) ∧
          stochastic_mst_query_eligible G Z D e := by
      intro e h
      have he := List.find?_some h
      simp only [decide_eq_true_eq] at he
      exact ⟨Finset.mem_filter.mpr ⟨(SimpleGraph.mem_edgeFinset).mpr he.1, he⟩, he⟩
    split
    · rename_i hne
      split
      · rename_i h
        exfalso
        obtain ⟨e, he⟩ := hne
        rw [Finset.mem_filter] at he
        rw [List.find?_eq_none] at h
        have := h e (hπ e he.1)
        simp only [decide_eq_true_eq] at this
        exact this he.2
      · rename_i e h
        obtain ⟨hmem, he⟩ := key e h
        refine le_trans (Finset.inf'_le _ hmem) ?_
        have h1 := hp e he.1
        have h2 := mul_le_mul_of_nonneg_left (ih Z (insert e D)) h1.1
        have h3 := mul_le_mul_of_nonneg_left (ih (insert e Z) D) (sub_nonneg.mpr h1.2)
        try simp only
        linarith
    · rename_i hne
      split
      · exact le_refl _
      · rename_i e h
        exact absurd ⟨e, (key e h).1⟩ hne

theorem stochastic_mst_adaptive_cost_le_priority_cost {V : Type*} [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (p : Sym2 V → ℝ)
    (hp : ∀ e ∈ G.edgeSet, 0 ≤ p e ∧ p e ≤ 1) :
    stochastic_mst_adaptive_cost G p ≤ stochastic_mst_priority_cost G p := by
  unfold stochastic_mst_priority_cost
  refine le_csInf ⟨_, G.edgeFinset.toList, List.Perm.refl _, rfl⟩ ?_
  rintro x ⟨π, hπ, rfl⟩
  exact stochastic_mst_adaptive_cost_aux_le_priority_cost_aux G p hp π
    (fun e he => hπ.mem_iff.mpr (Finset.mem_toList.mpr he)) _ ∅ ∅
See it in the graphDiscuss this resultChallenge it