Proof of Lemma 6.3 — the two smallest set sums total at most half
ProvedTreewidthApprox.Partition.merge_stepbalanced-partitioncombinatoricsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let sets have nonnegative integer sums . Select two distinct sets whose sums are each no greater than every other set's sum. Then
This is the bound on a single merge in the paper's three-partition observation.
Formalization Note The finite family may contain zero sums. The two selected indices are distinct; their order is irrelevant.
Preamble
import Mathlib
Formal statement
namespace TreewidthApprox.Partition
/-- Proof of Lemma 6.3, p. 364: among at least four set sums, the two smallest
together account for at most half of the total. -/
theorem merge_step (m : ℕ) (hm : 4 ≤ m) (b : Fin m → ℕ) (i j : Fin m) (hij : i ≠ j)
(hmin : ∀ l, l ≠ i → l ≠ j → b i ≤ b l ∧ b j ≤ b l) :
2 * (b i + b j) ≤ ∑ l, b l := by sorry
end TreewidthApprox.Partition
Source
Bodlaender, Drange, Dregi, Fomin, Lokshtanov and Pilipczuk, A c^k n 5-approximation algorithm for treewidth, SIAM J. Comput. 45(2) (2016), p. 364, proof of Lemma 6.3, merge paragraph, https://doi.org/10.1137/130947374
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.