List operations compute the named vertex sets and external boundaries
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.binary_block_set_testsalgorithmsclusteringdynamic-programming
Subset, equality, intersection, external neighborhood, and the number of distinct vertices are computed exactly on sparse or repeated labels.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_BinaryBlockSearch open StableMSR.Recovery StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch open StableMSR.Recovery.DecompositionSearch RobertsonSeymour1986.GM5
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.BlockSearch.binary_block_set_tests (z : GraphInput) :
(∀ s u, contained z s u=true ↔ cuts z s⊆cuts z u) ∧
(∀ s u, same z s u=true ↔ cuts z s=cuts z u) ∧
(∀ s u, meets z s u=true ↔ (cuts z s∩cuts z u).Nonempty) ∧
(∀ s, cuts z (border z s)=boundary (scopeGraph z.1 z.2) (cuts z s)) ∧
(names z.1).length=Fintype.card (Vertex z) := by
sorry
Source
Constructive binary implementation of the tight-block recurrence in StableMSR.Recovery.DecompositionSearch.finite_decomposition_search, https://prove2.me/theorems/d4f2a14a-b18f-44f7-966a-d1411797cf17.