Lemma 2.1 — a minimal transversal of has at most vertices
ProvedCutSetEnum.lemma_2_1combinatorial-optimizationhypergraph-k-cutp2o-gran-per-chapterp2o-plan-paperp2o-v1submodularityterminal-cuts
Let be a hypergraph, , and a 2-partition of with . Let
and let be an inclusion-wise minimal subset of that meets every member of . Then
With Proposition 2.1 this gives Theorem 2.1. The proof is by contradiction through Claims 2.1–2.6 and the strict conclusion of Theorem 1.5.
Differences from the source:
- 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
Preamble
import Mathlib import Definitions.Def_HyperKCut_Structure_Model import Definitions.Def_CutSetEnum_IsOptKCutValue import Definitions.Def_CutSetEnum_Coll import Definitions.Def_CutSetEnum_IsMinTransversal open HyperKCut.Structure
Formal statement
namespace CutSetEnum
variable {V : Type} [Fintype V] [DecidableEq V]
/-- **Lemma 2.1: a minimal transversal of `C` has at most `2k − 1` vertices.**
Beideman, Chandrasekaran & Wang, arXiv:2204.09178v2, Lemma 2.1, p.11 (PDF 12), in the setting of
the proof of 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. … Consider the collection C := {Q ⊆ V : Ū ⊊ Q, d(Q) ≤ d(U), and
δ(Q) ≠ δ(U)}. Let S be an inclusion-wise minimal subset of U such that S ∩ Q ≠ ∅ for all Q ∈ C …
Lemma 2.1. The size of the subset S is at most 2k − 1."
**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)`. `S` is any minimal transversal of `C = Coll H U` inside `U`
(`IsMinTransversal`); the statement holds for every such `S`. `2 * k - 1` is natural-number
subtraction, harmless since `k ≥ 2`. -/
theorem lemma_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) (hS : IsMinTransversal H U S) :
S.card ≤ 2 * k - 1 := 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, Lemma 2.1, p.11 (PDF 12); setting from Theorem 2.1, proof, p.10 (PDF 11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.