op_98_one_cluster_packing_bound
If every set o of a packing O has at most one conflict neighbour in A, then weight(O) ≤ 2·weight(A). Each o has exactly one neighbour a (the singleton-square condition excludes zero), so O splits into the fibres Fib a = {o ∈ O : N(A,{o}) = {a}}; each fibre is a packing of at most |a| ≤ 4 sets all conflicting with a, so N(A, Fib a) = {a} and the factor-2 exchange inequality gives weight(Fib a) ≤ 2·weight a. Summing over the pairwise disjoint fibres gives the claim.
Statement
theorem op_98_one_cluster_packing_bound {α : Type*} [DecidableEq α] (inst : WeightedSetPackingInstance α 4) (A O : Finset (Finset α)) (hA : is_square_locally_optimal inst 4 A) (hO : is_packing inst O) (h1 : ∀ o ∈ O, (conflict_neighborhood A {o}).card ≤ 1) : 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 8
- 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…
- op_98_conflict_degree_boundA set a conflicts with at most a.card sets of any packing O: the intersections o ∩ a (o ∈ O, o not disjoint from a) are nonempty, pairwise…
- WeightedSetPackingInstanceFor a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists of a…
- squared_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the squared-weight potential squared_weight inst 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_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 α)),…
- 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…
The proof, explained
The theorem establishes that any packing O whose sets each have at most one conflict neighbor in a square locally optimal packing A satisfies weight(O) ≤ 2 · weight(A). By testing the square local optimality condition against singletons, every set in O must conflict with at least one set in A, which forces each competitor set to have exactly one conflict neighbor in A. This partitions O into pairwise disjoint fibers Fib(a) = {o ∈ O : N(A, {o}) = {a}}. Each fiber is a packing of at most |a| ≤ 4 sets whose conflict neighborhood in A is exactly {a}, so the factor-2 square exchange inequality bounds its weight by 2 · weight(a). Summing this bound over all a ∈ A completes the proof.
The set A is a valid packing, and any candidate packing X with |X| ≤ 4 satisfies the square exchange inequality against its conflict neighborhood in A.
Unpack the definition of square local optimality into its two parts: A is a packing (`hAp`), and every packing X with cardinality at most 4 satisfies the squared weight inequality against its conflict neighborhood in A (`hloc`).
have hAp : is_packing inst A := hA.1 have hloc := hA.2
A set b belongs to the conflict neighborhood of X if and only if b ∈ A and b intersects some x ∈ X; for a singleton X = {o}, this means b ∈ A and b is not disjoint from o.
Unfolding the definition of `conflict_neighborhood` gives the characterisation for general X. Specializing X to the singleton {o} reduces the existential condition to the single intersection non-disjointness condition ¬ Disjoint b o.
uses
Finset.mem_filter,Finset.mem_singleton,Finset.mem_singleton_selfhave hmemN : ∀ (b : Finset α) (X : Finset (Finset α)), b ∈ conflict_neighborhood A X ↔ b ∈ A ∧ ∃ x ∈ X, ¬ Disjoint b x := by intro b X simp only [conflict_neighborhood, Finset.mem_filter] have hmemS : ∀ (b o : Finset α), b ∈ conflict_neighborhood A {o} ↔ b ∈ A ∧ ¬ Disjoint b o := by intro b o rw [hmemN] constructor · rintro ⟨hb, x, hx, hnd⟩ rw [Finset.mem_singleton] at hx exact ⟨hb, hx ▸ hnd⟩ · rintro ⟨hb, hnd⟩ exact ⟨hb, o, Finset.mem_singleton_self o, hnd⟩
Every competitor set o ∈ O has a nonempty conflict neighborhood in A.
Assume for contradiction that some o ∈ O has an empty conflict neighborhood in A. The singleton {o} is a packing of size 1 ≤ 4, so by local optimality of A, (weight o)^2 ≤ 0. But all weights in the instance are strictly positive, giving (weight o)^2 > 0, an immediate contradiction.
uses
Finset.not_nonempty_iff_eq_empty,Finset.mem_singleton,Finset.mem_coe,Finset.card_singleton,Finset.sum_singleton,Finset.sum_emptyhave hne : ∀ o ∈ O, (conflict_neighborhood A {o}).Nonempty := by intro o ho by_contra hemp rw [Finset.not_nonempty_iff_eq_empty] at hemp have hsub : ({o} : Finset (Finset α)) ⊆ inst.family := by intro x hx rw [Finset.mem_singleton] at hx subst hx exact hO.1 ho have hp : is_packing inst ({o} : Finset (Finset α)) := by refine ⟨hsub, ?_⟩ intro x hx y hy hne' simp only [Finset.mem_coe, Finset.mem_singleton] at hx hy exact absurd (hx.trans hy.symm) hne' have h4 : ({o} : Finset (Finset α)).card ≤ 4 := by simp only [Finset.card_singleton]; norm_num have key := hloc {o} hp h4 rw [squared_weight, squared_weight, Finset.sum_singleton, hemp, Finset.sum_empty] at key have hpos : 0 < inst.weight o := inst.weight_pos o (hO.1 ho) nlinarith
Every competitor set o ∈ O has exactly one conflict neighbor a ∈ A, so N(A, {o}) = {a}.
Since the conflict neighborhood of {o} is nonempty, its cardinality is at least 1. By hypothesis h1, its cardinality is at most 1, so it is exactly 1. Hence N(A, {o}) = {a} for a unique element a, which lies in A by definition of conflict neighborhoods.
uses
Finset.card_pos.mpr,Finset.card_eq_one.mp,Finset.mem_singleton_selfhave huniq : ∀ o ∈ O, ∃ a ∈ A, conflict_neighborhood A {o} = {a} := by intro o ho have hcpos : 0 < (conflict_neighborhood A {o}).card := Finset.card_pos.mpr (hne o ho) have hcle := h1 o ho have hc : (conflict_neighborhood A {o}).card = 1 := by omega obtain ⟨a, ha⟩ := Finset.card_eq_one.mp hc refine ⟨a, ?_, ha⟩ have : a ∈ conflict_neighborhood A {o} := by rw [ha]; exact Finset.mem_singleton_self a exact (hmemS a o).mp this |>.1
The packing O is covered by the fibers Fib(a) = {o ∈ O : N(A, {o}) = {a}} over all a ∈ A.
Define each fiber Fib(a) as the sets in O whose sole conflict neighbor in A is a. Each fiber is contained in O, and every o ∈ O belongs to Fib(a) for the unique neighbor a ∈ A established previously, so the union of fibers over A equals O.
uses
Finset.mem_filter,Finset.mem_biUnionset Fib : Finset α → Finset (Finset α) := fun a => O.filter (fun o => conflict_neighborhood A {o} = {a}) with hFib have hFib_mem : ∀ a o, o ∈ Fib a ↔ o ∈ O ∧ conflict_neighborhood A {o} = {a} := by intro a o; simp only [hFib, Finset.mem_filter] have hFib_sub : ∀ a, Fib a ⊆ O := by intro a o ho; exact (hFib_mem a o).mp ho |>.1 have hcover : A.biUnion Fib = O := by ext o rw [Finset.mem_biUnion] constructor · rintro ⟨a, _, ho⟩; exact hFib_sub a ho · intro ho obtain ⟨a, haA, ha⟩ := huniq o ho exact ⟨a, haA, (hFib_mem a o).mpr ⟨ho, ha⟩⟩
The fibers Fib(a) are pairwise disjoint for distinct a ∈ A, and the total weight of O is the sum of the weights of the fibers.
If an element o ∈ O belonged to both Fib(a) and Fib(b), then {a} = N(A, {o}) = {b}, forcing a = b. Since the fibers form a disjoint partition of O, the total weight of O decomposes as the sum over a ∈ A of the packing weight of Fib(a).
uses
Finset.disjoint_left,Finset.singleton_inj.mp,Finset.sum_biUnionhave hpdisj : (↑A : Set (Finset α)).PairwiseDisjoint Fib := by intro a haA b hbA hne' change Disjoint (Fib a) (Fib b) rw [Finset.disjoint_left] intro o hoa hob have h1a : conflict_neighborhood A {o} = {a} := (hFib_mem a o).mp hoa |>.2 have h1b : conflict_neighborhood A {o} = {b} := (hFib_mem b o).mp hob |>.2 have : a = b := by rw [h1b] at h1a exact (Finset.singleton_inj.mp h1a).symm exact hne' this have hsum1 : packing_weight inst O = ∑ a ∈ A, packing_weight inst (Fib a) := by simp only [packing_weight] rw [← hcover] exact Finset.sum_biUnion (f := fun s => inst.weight s) hpdisj
For each a ∈ A, the packing weight of Fib(a) is at most 2 · weight(a).
If Fib(a) is empty, its weight is 0 ≤ 2 · weight(a). If Fib(a) is nonempty, it is a sub-packing of O whose sets all conflict with a, so |Fib(a)| ≤ |a| ≤ 4 by the conflict degree bound. Moreover, the conflict neighborhood of Fib(a) in A is precisely {a}, because a conflicts with every set in Fib(a), while any other b ∈ A conflicting with some o ∈ Fib(a) would have to belong to N(A, {o}) = {a}, forcing b = a. The factor-2 exchange bound for packings of size at most 4 then yields weight(Fib(a)) ≤ 2 · weight(N(A, Fib(a))) = 2 · weight(a).
uses
Finset.sum_empty,Finset.mem_filter,Finset.mem_singleton_self,Finset.card_le_card,op_98_conflict_degree_bound,Finset.eq_singleton_iff_unique_mem,Finset.nonempty_iff_ne_empty.mpr,Finset.mem_singleton,op_98_sq_exchange_boundhave hterm : ∀ a ∈ A, packing_weight inst (Fib a) ≤ 2 * inst.weight a := by intro a haA have hwa : 0 < inst.weight a := inst.weight_pos a (hAp.1 haA) by_cases hemp : Fib a = ∅ · rw [hemp, packing_weight, Finset.sum_empty] linarith · have hpk : is_packing inst (Fib a) := ⟨fun x hx => hO.1 (hFib_sub a hx), fun x hx y hy hne' => hO.2 (hFib_sub a hx) (hFib_sub a hy) hne'⟩ have hc4 : (Fib a).card ≤ 4 := by have hsub : Fib a ⊆ O.filter (fun o => ¬ Disjoint a o) := by intro o ho rw [Finset.mem_filter] refine ⟨(hFib_mem a o).mp ho |>.1, ?_⟩ have hconf : conflict_neighborhood A {o} = {a} := (hFib_mem a o).mp ho |>.2 have hmem : a ∈ conflict_neighborhood A {o} := by rw [hconf]; exact Finset.mem_singleton_self a exact (hmemS a o).mp hmem |>.2 calc (Fib a).card ≤ (O.filter (fun o => ¬ Disjoint a o)).card := Finset.card_le_card hsub _ ≤ a.card := op_98_conflict_degree_bound inst O a hO _ ≤ 4 := inst.card_le a (hAp.1 haA) have hN : conflict_neighborhood A (Fib a) = {a} := by rw [Finset.eq_singleton_iff_unique_mem] refine ⟨?_, ?_⟩ · rw [hmemN] refine ⟨haA, ?_⟩ obtain ⟨o, ho⟩ := Finset.nonempty_iff_ne_empty.mpr hemp refine ⟨o, ho, ?_⟩ have hconf : conflict_neighborhood A {o} = {a} := (hFib_mem a o).mp ho |>.2 have hmem : a ∈ conflict_neighborhood A {o} := by rw [hconf]; exact Finset.mem_singleton_self a exact (hmemS a o).mp hmem |>.2 · intro b hb rw [hmemN] at hb obtain ⟨hbA, o, ho, hnd⟩ := hb have hconf : conflict_neighborhood A {o} = {a} := (hFib_mem a o).mp ho |>.2 have hmem : b ∈ conflict_neighborhood A {o} := (hmemS b o).mpr ⟨hbA, hnd⟩ rw [hconf, Finset.mem_singleton] at hmem exact hmem have hbound := op_98_sq_exchange_bound inst A (Fib a) hA hpk hc4 rw [hN] at hbound simpa [packing_weight] using hbound
The total packing weight of O is at most 2 · packing_weight(A).
Summing the fiber bound weight(Fib(a)) ≤ 2 · weight(a) over all a ∈ A and factoring out the scalar 2 converts the sum of fiber weights directly into 2 · packing_weight(A).
uses
Finset.sum_le_sum,Finset.mul_sumcalc packing_weight inst O = ∑ a ∈ A, packing_weight inst (Fib a) := hsum1 _ ≤ ∑ a ∈ A, 2 * inst.weight a := Finset.sum_le_sum hterm _ = 2 * packing_weight inst A := by rw [packing_weight, Finset.mul_sum]
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the base set and satisfies the filtering predicate.
Finset.mem_singleton- An element belongs to a singleton set {a} if and only if it equals a.
Finset.mem_singleton_self- Any element a belongs to the singleton set {a}.
Finset.not_nonempty_iff_eq_empty- A finite set is not nonempty if and only if it is empty.
Finset.mem_coe- Membership in a finite set coerced to a set is equivalent to membership in the finite set.
Finset.card_singleton- The cardinality of a singleton set is 1.
Finset.sum_singleton- The sum of a function over a singleton set {a} equals the function value at a.
Finset.sum_empty- The sum of any function over the empty set is 0.
Finset.card_pos.mpr- If a finite set is nonempty, its cardinality is strictly greater than 0.
Finset.card_eq_one.mp- If a finite set has cardinality 1, it is a singleton set {a} for some element a.
Finset.mem_biUnion- An element belongs to a union of sets indexed by a finite set if and only if it belongs to the set at some index.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first set belongs to the second.
Finset.singleton_inj.mp- If two singleton sets {a} and {b} are equal, then a = b.
Finset.sum_biUnion- The sum of a function over a pairwise disjoint union of finite sets equals the sum of the sums over each constituent set.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most the cardinality of the other.
op_98_conflict_degree_bound- In a weighted set packing instance, the number of sets in a packing O that intersect a given set a is at most the cardinality of a.
Finset.eq_singleton_iff_unique_mem- A finite set s equals {a} if and only if a belongs to s and every element of s equals a.
Finset.nonempty_iff_ne_empty.mpr- A finite set is nonempty if it is not equal to the empty set.
op_98_sq_exchange_bound- For a square locally optimal packing A and any packing X of size at most 4, the weight of X is at most twice the weight of its conflict neighborhood in A.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i of a finite set, then the sum of f over that set is at most the sum of g.
Finset.mul_sum- Multiplication distributes over finite sums: a * ∑ i, f(i) = ∑ i, a * f(i).
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.
/-- Ratio-2 bound in the star-cluster regime where every competitor set has exactly one conflict neighbour. -/theorem op_98_one_cluster_packing_bound {α : Type*} [DecidableEq α] (inst : WeightedSetPackingInstance α 4) (A O : Finset (Finset α)) (hA : is_square_locally_optimal inst 4 A) (hO : is_packing inst O) (h1 : ∀ o ∈ O, (conflict_neighborhood A {o}).card ≤ 1) : packing_weight inst O ≤ 2 * packing_weight inst A := by have hAp : is_packing inst A := hA.1 have hloc := hA.2 have hmemN : ∀ (b : Finset α) (X : Finset (Finset α)), b ∈ conflict_neighborhood A X ↔ b ∈ A ∧ ∃ x ∈ X, ¬ Disjoint b x := by intro b X simp only [conflict_neighborhood, Finset.mem_filter] have hmemS : ∀ (b o : Finset α), b ∈ conflict_neighborhood A {o} ↔ b ∈ A ∧ ¬ Disjoint b o := by intro b o rw [hmemN] constructor · rintro ⟨hb, x, hx, hnd⟩ rw [Finset.mem_singleton] at hx exact ⟨hb, hx ▸ hnd⟩ · rintro ⟨hb, hnd⟩ exact ⟨hb, o, Finset.mem_singleton_self o, hnd⟩ have hne : ∀ o ∈ O, (conflict_neighborhood A {o}).Nonempty := by intro o ho by_contra hemp rw [Finset.not_nonempty_iff_eq_empty] at hemp have hsub : ({o} : Finset (Finset α)) ⊆ inst.family := by intro x hx rw [Finset.mem_singleton] at hx subst hx exact hO.1 ho have hp : is_packing inst ({o} : Finset (Finset α)) := by refine ⟨hsub, ?_⟩ intro x hx y hy hne' simp only [Finset.mem_coe, Finset.mem_singleton] at hx hy exact absurd (hx.trans hy.symm) hne' have h4 : ({o} : Finset (Finset α)).card ≤ 4 := by simp only [Finset.card_singleton]; norm_num have key := hloc {o} hp h4 rw [squared_weight, squared_weight, Finset.sum_singleton, hemp, Finset.sum_empty] at key have hpos : 0 < inst.weight o := inst.weight_pos o (hO.1 ho) nlinarith have huniq : ∀ o ∈ O, ∃ a ∈ A, conflict_neighborhood A {o} = {a} := by intro o ho have hcpos : 0 < (conflict_neighborhood A {o}).card := Finset.card_pos.mpr (hne o ho) have hcle := h1 o ho have hc : (conflict_neighborhood A {o}).card = 1 := by omega obtain ⟨a, ha⟩ := Finset.card_eq_one.mp hc refine ⟨a, ?_, ha⟩ have : a ∈ conflict_neighborhood A {o} := by rw [ha]; exact Finset.mem_singleton_self a exact (hmemS a o).mp this |>.1 set Fib : Finset α → Finset (Finset α) := fun a => O.filter (fun o => conflict_neighborhood A {o} = {a}) with hFib have hFib_mem : ∀ a o, o ∈ Fib a ↔ o ∈ O ∧ conflict_neighborhood A {o} = {a} := by intro a o; simp only [hFib, Finset.mem_filter] have hFib_sub : ∀ a, Fib a ⊆ O := by intro a o ho; exact (hFib_mem a o).mp ho |>.1 have hcover : A.biUnion Fib = O := by ext o rw [Finset.mem_biUnion] constructor · rintro ⟨a, _, ho⟩; exact hFib_sub a ho · intro ho obtain ⟨a, haA, ha⟩ := huniq o ho exact ⟨a, haA, (hFib_mem a o).mpr ⟨ho, ha⟩⟩ have hpdisj : (↑A : Set (Finset α)).PairwiseDisjoint Fib := by intro a haA b hbA hne' change Disjoint (Fib a) (Fib b) rw [Finset.disjoint_left] intro o hoa hob have h1a : conflict_neighborhood A {o} = {a} := (hFib_mem a o).mp hoa |>.2 have h1b : conflict_neighborhood A {o} = {b} := (hFib_mem b o).mp hob |>.2 have : a = b := by rw [h1b] at h1a exact (Finset.singleton_inj.mp h1a).symm exact hne' this have hsum1 : packing_weight inst O = ∑ a ∈ A, packing_weight inst (Fib a) := by simp only [packing_weight] rw [← hcover] exact Finset.sum_biUnion (f := fun s => inst.weight s) hpdisj have hterm : ∀ a ∈ A, packing_weight inst (Fib a) ≤ 2 * inst.weight a := by intro a haA have hwa : 0 < inst.weight a := inst.weight_pos a (hAp.1 haA) by_cases hemp : Fib a = ∅ · rw [hemp, packing_weight, Finset.sum_empty] linarith · have hpk : is_packing inst (Fib a) := ⟨fun x hx => hO.1 (hFib_sub a hx), fun x hx y hy hne' => hO.2 (hFib_sub a hx) (hFib_sub a hy) hne'⟩ have hc4 : (Fib a).card ≤ 4 := by have hsub : Fib a ⊆ O.filter (fun o => ¬ Disjoint a o) := by intro o ho rw [Finset.mem_filter] refine ⟨(hFib_mem a o).mp ho |>.1, ?_⟩ have hconf : conflict_neighborhood A {o} = {a} := (hFib_mem a o).mp ho |>.2 have hmem : a ∈ conflict_neighborhood A {o} := by rw [hconf]; exact Finset.mem_singleton_self a exact (hmemS a o).mp hmem |>.2 calc (Fib a).card ≤ (O.filter (fun o => ¬ Disjoint a o)).card := Finset.card_le_card hsub _ ≤ a.card := op_98_conflict_degree_bound inst O a hO _ ≤ 4 := inst.card_le a (hAp.1 haA) have hN : conflict_neighborhood A (Fib a) = {a} := by rw [Finset.eq_singleton_iff_unique_mem] refine ⟨?_, ?_⟩ · rw [hmemN] refine ⟨haA, ?_⟩ obtain ⟨o, ho⟩ := Finset.nonempty_iff_ne_empty.mpr hemp refine ⟨o, ho, ?_⟩ have hconf : conflict_neighborhood A {o} = {a} := (hFib_mem a o).mp ho |>.2 have hmem : a ∈ conflict_neighborhood A {o} := by rw [hconf]; exact Finset.mem_singleton_self a exact (hmemS a o).mp hmem |>.2 · intro b hb rw [hmemN] at hb obtain ⟨hbA, o, ho, hnd⟩ := hb have hconf : conflict_neighborhood A {o} = {a} := (hFib_mem a o).mp ho |>.2 have hmem : b ∈ conflict_neighborhood A {o} := (hmemS b o).mpr ⟨hbA, hnd⟩ rw [hconf, Finset.mem_singleton] at hmem exact hmem have hbound := op_98_sq_exchange_bound inst A (Fib a) hA hpk hc4 rw [hN] at hbound simpa [packing_weight] using hbound calc packing_weight inst O = ∑ a ∈ A, packing_weight inst (Fib a) := hsum1 _ ≤ ∑ a ∈ A, 2 * inst.weight a := Finset.sum_le_sum hterm _ = 2 * packing_weight inst A := by rw [packing_weight, Finset.mul_sum]