AFTD Auto-Formalizing Theoretical Domains

op_98_one_cluster_packing_bound

theoremverified

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.

  1. 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`).

    lines 7–8

      have hAp : is_packing inst A := hA.1
      have hloc := hA.2
  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.

    lines 9–22

    uses Finset.mem_filter, Finset.mem_singleton, Finset.mem_singleton_self

      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⟩
  3. 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.

    lines 23–42

    uses Finset.not_nonempty_iff_eq_empty, Finset.mem_singleton, Finset.mem_coe, Finset.card_singleton, Finset.sum_singleton, Finset.sum_empty

      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
  4. 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.

    lines 43–52

    uses Finset.card_pos.mpr, Finset.card_eq_one.mp, Finset.mem_singleton_self

      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
  5. 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.

    lines 53–66

    uses Finset.mem_filter, Finset.mem_biUnion

      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⟩⟩
  6. 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).

    lines 67–81

    uses Finset.disjoint_left, Finset.singleton_inj.mp, Finset.sum_biUnion

      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
  7. 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).

    lines 82–123

    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_bound

      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
  8. 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).

    lines 124–127

    uses Finset.sum_le_sum, Finset.mul_sum

      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]
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

/-- 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]
See it in the graphDiscuss this resultChallenge it