stochastic_mst_query_eligible
For 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 contracted, D those queried with weight 1, which are deleted) and an edge e (an element of Sym2 V), e is eligible for a query when: e is an edge of G, e is not in Z, e is not in D, and writing e = s(u, v), the vertices u and v are not joined by a path in the graph whose edges are exactly the elements of Z (so e is not a loop of the minor G/Z minus D), but are joined by a path in G after deleting e and the edges of D (so e is not a bridge of that minor).
Statement
def stochastic_mst_query_eligible {V : Type*} (G : SimpleGraph V) (Z D : Finset (Sym2 V)) (e : Sym2 V) : Prop
- Defined in
- arXiv:2610.40844 (Stochastic Minimum Spanning Tree Identification with Binary Weights), Sec. 2.1 and Lemma 2.2: the minor G_beta obtained by contracting 0-edges and deleting 1-edges; an edge is worth querying iff it is neither a loop nor a bridge of G_beta
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Used by 7
- 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),…
- tutte_strategy_solves_stochastic_mstFor any graph G, every Tutte strategy T for G solves the adaptive MST identification problem for G.
- stochastic_mst_adaptive_cost_le_priority_costFor 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…
- stochastic_mst_solves_auxFrom state (Z, D) of contracted edges Z and deleted edges D, a strategy solves the adaptive MST identification problem for G if at every…
- 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_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…
- stochastic_mst_is_tutte_auxFrom 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…
Read back from the Lean
For a type V, a simple graph G on V, finite sets of edges/pairs Z, D : Finset (Sym2 V), and an edge/pair e : Sym2 V, stochastic_mst_query_eligible G Z D e asserts that:
1. e is an edge of G (e ∈ G.edgeSet);
2. e is not in Z (e ∉ Z);
3. e is not in D (e ∉ D); and
4. there exist vertices u, v : V such that e = s(u, v) (i.e., u and v are the endpoints of e),
- u and v are not reachable from each other in the simple graph with edge set Z (SimpleGraph.fromEdgeSet ↑Z), and
- u and v are reachable from each other in the graph obtained from G by deleting the edge e and all edges in D (G.deleteEdges (insert e ↑D)).
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
def stochastic_mst_query_eligible {V : Type*} (G : SimpleGraph V) (Z D : Finset (Sym2 V)) (e : Sym2 V) : Prop := e ∈ G.edgeSet ∧ e ∉ Z ∧ e ∉ D ∧ ∃ u v : V, e = s(u, v) ∧ ¬ (SimpleGraph.fromEdgeSet (↑Z : Set (Sym2 V))).Reachable u v ∧ (G.deleteEdges (insert e (↑D : Set (Sym2 V)))).Reachable u v