Theorem 1.5, conclusion 2 — strict partition uncrossing
ProvedCutSetEnum.theorem_1_5_strictLet be a hypergraph, an integer and . Let be distinct vertices. For each let be a minimum -terminal cut (so is the source side), and suppose for every . Put
If some hyperedge meets , meets and is contained in , then there is a -partition of with such that
Conclusion 1 of the same theorem (the non-strict inequality, without the hyperedge ) is the published HyperKCut.Structure.theorem_3_1. The strict form is what the proof of Lemma 2.1 uses to produce a -partition cheaper than . The paper cites it from Beideman, Chandrasekaran and Wang (SODA 2022, reference [7]) and does not prove it.
Formalization Note The hypotheses are copied from theorem_3_1; A i is the sink side and the source side is (A i)ᶜ. The bound is written as for all . is P ⟨k-1, _⟩.
Differences from the source:
- reading: “the inequality in the previous conclusion is strict” → one k-partition P with Ū ⊊ P_k satisfies the strict bound; reason: the strict claim is about the partition of conclusion 1, which carries Ū ⊊ P_k; this is how Lemma 2.1's proof uses it
- encoding: |δ(P)| < ½ min{d(Aᵢ) + d(Aⱼ) : i ≠ j} → ∀ i ≠ j, 2 · cost H P < d(Aᵢ) + d(Aⱼ); reason: equivalent; the minimum is over a non-empty finite set since p ≥ 2
- encoding: S = {u₁, …, u_p}, indices 1…p; W and Z defined in the statement → injective u : Fin p → V (0-based); W, Z binders pinned by equations hW, hZ; reason: relabelling; same sets
- 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
import Mathlib import Definitions.Def_HyperKCut_Structure_Model open HyperKCut.Structure
namespace CutSetEnum
variable {V : Type} [Fintype V] [DecidableEq V]
/-- **Theorem 1.5, conclusion 2 (strict partition uncrossing).**
Beideman, Chandrasekaran & Wang, arXiv:2204.09178v2, Theorem 1.5, p.10 (PDF 11), cited there
from [7] (Beideman, Chandrasekaran & Wang, SODA 2022); this paper does not prove it:
"Let G = (V, E) be a hypergraph, k ≥ 2 be an integer and ∅ ≠ R ⊊ U ⊊ V. Let
S = {u₁, …, u_p} ⊆ U \ R for p ≥ 2k − 2. Let (Āᵢ, Aᵢ) be a minimum ((S ∪ R) \ {uᵢ}, Ū)-terminal
cut. Suppose that uᵢ ∈ Aᵢ \ (∪_{j∈[p]\{i}} Aⱼ) for every i ∈ [p]. Then, the following two hold:
1. There exists a k-partition (P₁, …, P_k) of V with Ū ⊊ P_k such that
|δ(P₁, …, P_k)| ≤ ½ min{d(Aᵢ) + d(Aⱼ) : i, j ∈ [p], i ≠ j}.
2. Moreover, if there exists a hyperedge e ∈ E such that e intersects W := ∪_{1≤i<j≤p}(Aᵢ ∩ Aⱼ),
e intersects Z := ∩_{i∈[p]} Āᵢ, and e is contained in W ∪ Z, then the inequality in the previous
conclusion is strict."
This is conclusion 2. The hypotheses are exactly those of the published
`HyperKCut.Structure.theorem_3_1` (conclusion 1), plus the hyperedge `e`.
**Formalization Note.** `A i` is the sink side `Aᵢ`; the source side `Āᵢ` is `(A i)ᶜ`, so
`IsMinTerminalCut H ((S ∪ R) \ {u i}) Uᶜ (A i)ᶜ`. Indices are `Fin p` (0-based); `u` is
injective, so `S` has exactly `p` elements. The k-partition is `P : Fin k → Finset V` with last
part `P ⟨k - 1, _⟩ = P_k`. The bound `|δ(P)| < ½ min{d(Aᵢ) + d(Aⱼ) : i ≠ j}` is written
`2 · cost H P < d(Aᵢ) + d(Aⱼ)` for all `i ≠ j` (the minimum is over a non-empty finite set since
`p ≥ 2`). "The inequality is strict" means: one k-partition with `Ū ⊊ P_k` satisfies the strict
bound. `W` and `Z` are binders pinned by `hW` and `hZ`. -/
theorem theorem_1_5_strict (H : HyperKCut.Structure.Hypergraph V) (k p : ℕ)
(hk : 2 ≤ k) (hp : 2 * k - 2 ≤ p)
(R U : Finset V) (hR : R.Nonempty) (hRU : R ⊂ U)
(hUV : U ⊂ (Finset.univ : Finset V))
(u : Fin p → V) (huinj : Function.Injective u)
(hu : ∀ i, u i ∈ U \ R)
(A : Fin p → Finset V)
(hA : ∀ i, IsMinTerminalCut H
(((Finset.univ.image u) ∪ R).erase (u i)) Uᶜ (A i)ᶜ)
(hui : ∀ i, u i ∈ A i)
(huj : ∀ i j, i ≠ j → u i ∉ A j)
(W Z : Finset V)
(hW : W = (Finset.univ.filter (fun ij : Fin p × Fin p => ij.1 < ij.2)).biUnion
(fun ij => A ij.1 ∩ A ij.2))
(hZ : Z = Finset.univ.inf (fun i => (A i)ᶜ))
(e : Finset V) (he : e ∈ H.edges)
(heW : Meets e W) (heZ : Meets e Z) (heWZ : e ⊆ W ∪ Z) :
∃ P : Fin k → Finset V, IsPartition P ∧
Uᶜ ⊂ P ⟨k - 1, by omega⟩ ∧
∀ i j : Fin p, i ≠ j → 2 * cost H P < d H (A i) + d H (A j) := by sorry
end CutSetEnum
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.