op_98_small_packing_bound
Special case of the target: when the competing packing has at most 4 sets, weight(O) ≤ 2·weight(A), so c = 2 with the empty repair family suffices.
Statement
theorem op_98_small_packing_bound {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A O : Finset (Finset α)) (hA : is_square_locally_optimal inst 4 A) (hO : is_packing inst O) (hOc : O.card ≤ 4) : packing_weight inst O ≤ 2 * packing_weight inst A
- Source
- step towards op_98_objective_switching_weighted_four_set_packing
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- op_98_sq_exchange_boundObjective switching, first half: square local optimality turns the squared potential inequality for exchanges of at most 4 sets into a…
- WeightedSetPackingInstanceFor a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists of a…
- packing_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the linear weight packing_weight inst A of a…
- is_square_locally_optimalGiven an instance inst of weighted k-set packing on a type α with decidable equality, a packing A is square locally optimal with respect…
- is_packingGiven an instance inst of weighted k-set packing on a type α with decidable equality, a sub-collection A : Finset (Finset α) is a packing…
- conflict_neighborhoodGiven a type α with decidable equality and two finite collections of finite subsets of α, A and X (both of type Finset (Finset α)),…
- squared_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the squared-weight potential squared_weight inst A…
The proof, explained
To bound the weight of any competing packing O with at most 4 sets by twice the weight of a square-locally optimal packing A, the proof first invokes the square-exchange bound (`op_98_sq_exchange_bound`) to bound the weight of O by twice the weight of its conflict neighborhood in A. Because the conflict neighborhood is a subcollection of A and all instance weights are positive, the weight of the conflict neighborhood is at most the weight of A. Linear arithmetic combines these two bounds to conclude that weight(O) ≤ 2 · weight(A).
The weight of the competitor packing O is at most twice the weight of its conflict neighborhood in A.
Applying `op_98_sq_exchange_bound` to A and O establishes that weight(O) ≤ 2 · weight(conflict_neighborhood A O), using the assumptions that A is square-locally optimal with parameter 4, O is a packing, and O contains at most 4 sets.
uses
op_98_sq_exchange_boundhave h1 : packing_weight inst O ≤ 2 * packing_weight inst (conflict_neighborhood A O) := op_98_sq_exchange_bound inst A O hA hO hOcThe conflict neighborhood of O in A is a subset of A.
By definition, the conflict neighborhood consists of those sets in A that intersect at least one set in O. Rewriting with `Finset.mem_filter`, any element in the conflict neighborhood is in particular an element of A.
uses
Finset.mem_filterhave hsub : conflict_neighborhood A O ⊆ A := by intro x hx simp only [conflict_neighborhood, Finset.mem_filter] at hx exact hx.1
The weight of the conflict neighborhood of O in A is at most the weight of A.
Expanding the definition of packing weight into sums of weights, the conflict neighborhood is a subcollection of A. Since A is a packing, its sets belong to the instance family and have strictly positive weights; in particular, by `le_of_lt`, their weights are nonnegative. Therefore, `Finset.sum_le_sum_of_subset_of_nonneg` shows that the sum over the subcollection is at most the sum over all of A.
uses
Finset.sum_le_sum_of_subset_of_nonneg,le_of_lthave h2 : packing_weight inst (conflict_neighborhood A O) ≤ packing_weight inst A := by rw [packing_weight, packing_weight] exact Finset.sum_le_sum_of_subset_of_nonneg hsub (fun x hx _ => le_of_lt (inst.weight_pos x (hA.1.1 hx)))
The weight of O is at most twice the weight of A. automation
Combining the inequality weight(O) ≤ 2 · weight(conflict_neighborhood A O) with weight(conflict_neighborhood A O) ≤ weight(A), linear arithmetic directly concludes that weight(O) ≤ 2 · weight(A).
linarith
op_98_sq_exchange_bound- In a weighted set packing instance, if a packing A is square-locally optimal with parameter 4, and X is a packing with at most 4 sets, then the weight of X is at most twice the weight of its conflict neighborhood in A.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the filter predicate.
Finset.sum_le_sum_of_subset_of_nonneg- If one finset is a subset of another and the summand is nonnegative on the difference, the sum over the subset is at most the sum over the superset.
le_of_lt- A strict inequality a < b implies the weak inequality a ≤ b.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Small-instance case: ratio 2 with no repairs when the competitor has at most 4 sets. -/theorem op_98_small_packing_bound {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A O : Finset (Finset α)) (hA : is_square_locally_optimal inst 4 A) (hO : is_packing inst O) (hOc : O.card ≤ 4) : packing_weight inst O ≤ 2 * packing_weight inst A := by have h1 : packing_weight inst O ≤ 2 * packing_weight inst (conflict_neighborhood A O) := op_98_sq_exchange_bound inst A O hA hO hOc have hsub : conflict_neighborhood A O ⊆ A := by intro x hx simp only [conflict_neighborhood, Finset.mem_filter] at hx exact hx.1 have h2 : packing_weight inst (conflict_neighborhood A O) ≤ packing_weight inst A := by rw [packing_weight, packing_weight] exact Finset.sum_le_sum_of_subset_of_nonneg hsub (fun x hx _ => le_of_lt (inst.weight_pos x (hA.1.1 hx))) linarith