Theorem 2.1 — some , , recovers against the sink
ProvedCutSetEnum.theorem_2_1combinatorial-optimizationhypergraph-k-cutp2o-gran-per-chapterp2o-plan-paperp2o-v1submodularityterminal-cuts
Let be a hypergraph and an integer, and let be a 2-partition of with . Then there is a non-empty set with
such that every minimum -terminal cut satisfies .
This is the one-sided half of Theorem 1.4: the sink terminal set is all of . It already settles Theorem 1.4 when .
Differences from the source:
- reading: “there exists a set S ⊆ U” → S ⊆ U and S non-empty; reason: (S, T)-terminal cuts are defined only for non-empty S (p.4); the stronger reading, and true: an empty witness can be replaced by any singleton {u} ⊆ U
- encoding: d(U) = OPT_k-cut (a minimum over k-partitions) → IsOptKCutValue H k (d H U): some k-partition has cost d(U) and none has less; reason: no sInf, so no junk value when V has fewer than k vertices; same instances
- encoding: (A, Ā) an (S, T)-terminal cut, a 2-partition with S ⊆ A ⊆ V \ T → published IsTerminalCut S T A := S ⊆ A ∧ Disjoint A T (no separate 2-partition clause); reason: for non-empty S and T the two coincide
- encoding: δ(A) = δ(U), equality of sets of hyperedges → cutSet H A = cutSet H U, equality of sub-multisets of the hyperedge multiset; reason: parallel copies of a hyperedge cross a cut together, so multiset and set equality agree
Preamble
import Mathlib import Definitions.Def_HyperKCut_Structure_Model import Definitions.Def_CutSetEnum_cutSet import Definitions.Def_CutSetEnum_IsOptKCutValue open HyperKCut.Structure
Formal statement
namespace CutSetEnum
variable {V : Type} [Fintype V] [DecidableEq V]
/-- **Theorem 2.1: a source set `S ⊆ U` with `|S| ≤ 2k − 1` recovers `δ(U)` against sink `Ū`.**
Beideman, Chandrasekaran & Wang, arXiv:2204.09178v2, Theorem 2.1, p.10 (PDF 11): "Let G = (V, E)
be a hypergraph and let OPT_k-cut be the optimum value of Hypergraph-k-Cut in G for some integer
k ≥ 2. Suppose (U, Ū) is a 2-partition of V with d(U) = OPT_k-cut. Then, there exists a set S ⊆ U
with |S| ≤ 2k − 1 such that every minimum (S, Ū)-terminal cut (A, Ā) satisfies δ(A) = δ(U)."
**Formalization Note.** `(U, Uᶜ)` is a 2-partition: `U` and `Uᶜ` non-empty. "d(U) = OPT_k-cut" is
`IsOptKCutValue H k (d H U)` (attained and least). The conclusion asserts `S` non-empty, because
the paper defines `(S, T)`-terminal cuts only for non-empty `S` and `T`. Terminal cuts are the
published `IsMinTerminalCut` (no separate 2-partition clause; equivalent for non-empty terminal
sets). The conclusion quantifies over **every** minimum `(S, Uᶜ)`-terminal cut and compares
cut-sets (`cutSet`, multiset equality), not cut values. -/
theorem theorem_2_1
(H : HyperKCut.Structure.Hypergraph V) (k : ℕ) (hk : 2 ≤ k)
(U : Finset V) (hU : U.Nonempty) (hUc : Uᶜ.Nonempty)
(hopt : IsOptKCutValue H k (d H U)) :
∃ S : Finset V, S ⊆ U ∧ S.Nonempty ∧ S.card ≤ 2 * k - 1 ∧
∀ A : Finset V, IsMinTerminalCut H S Uᶜ A → cutSet H A = cutSet H U := by sorry
end CutSetEnum
Source
Beideman, Chandrasekaran & Wang, Counting and enumerating optimum cut sets for hypergraph k-partitioning problems for fixed k, arXiv:2204.09178v2, Theorem 2.1, p.10 (PDF 11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.