AFTD Auto-Formalizing Theoretical Domains

op_98_conflict_degree_bound

theoremverified

A 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 disjoint subsets of a.

Statement

theorem op_98_conflict_degree_bound {α : Type*} [DecidableEq α] {k : ℕ}
    (inst : WeightedSetPackingInstance α k) (O : Finset (Finset α)) (a : Finset α)
    (hO : is_packing inst O) :
    (O.filter (fun o => ¬ Disjoint a o)).card ≤ a.card
Source
step towards op_98_objective_switching_weighted_four_set_packing
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • WeightedSetPackingInstanceFor a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists 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…
Used by 4
  • op_98_eight_approximationPartition the packing O into blocks of at most 4 sets; the factor-2 exchange inequality gives weight(block) ≤ 2·weight(N(A, block)) for…
  • op_98_one_cluster_packing_boundIf 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…
  • op_98_conflict_deg_le_fourFor any weighted 4-set packing instance inst and packings A, O, if A is square locally optimal and o ∈ O, then (conflict_neighborhood A…
  • op_98_four_approximationEvery packing O satisfies packing_weight inst O ≤ 4 * packing_weight inst A under square local optimality with respect to 4-exchanges.

The proof, explained

To bound the number of sets in the packing O conflicting with a, let F be the subcollection of such sets. Because O is a packing, its elements are pairwise disjoint, making the intersections {o ∩ a | o ∈ F} pairwise disjoint, nonempty subsets of a. Consequently, |F| = ∑_{o ∈ F} 1 ≤ ∑_{o ∈ F} |o ∩ a| = |⋃_{o ∈ F} (o ∩ a)| ≤ |a|.

  1. Define F as the collection of sets in the packing O that intersect a, and characterize membership in F.

    We define F as the filter of O containing sets not disjoint from a. By the characteristic property of `Finset.filter` (`Finset.mem_filter`), an element o belongs to F if and only if o ∈ O and ¬ Disjoint a o.

    lines 6–8

    uses Finset.mem_filter

      set F := O.filter (fun o => ¬ Disjoint a o) with hF
      have hmem : ∀ o, o ∈ F ↔ o ∈ O ∧ ¬ Disjoint a o := by
        intro o; rw [hF, Finset.mem_filter]
  2. The intersections {o ∩ a | o ∈ F} are pairwise disjoint.

    Take distinct sets o, o' ∈ F. Since both belong to the packing O, they are disjoint by definition of a packing (hO.2). Because o ∩ a ⊆ o and o' ∩ a ⊆ o' by `Finset.inter_subset_left`, their intersections with a are also disjoint by monotonicity of disjointness (`Disjoint.mono`).

    lines 9–14

    uses Disjoint.mono, Finset.inter_subset_left

      have hpd : (F : Set (Finset α)).PairwiseDisjoint (fun o => o ∩ a) := by
        intro o ho o' ho' hne
        have hoO : o ∈ O := (hmem o).mp ho |>.1
        have ho'O : o' ∈ O := (hmem o').mp ho' |>.1
        exact Disjoint.mono Finset.inter_subset_left Finset.inter_subset_left
          (hO.2 hoO ho'O hne)
  3. The cardinality of the union ⋃_{o ∈ F} (o ∩ a) equals the sum of cardinalities ∑_{o ∈ F} |o ∩ a|.

    Since the family {o ∩ a}_{o ∈ F} is pairwise disjoint, the size of its union is the sum of the sizes of each member (`Finset.card_biUnion`).

    lines 15–16

    uses Finset.card_biUnion

      have hcard : (F.biUnion (fun o => o ∩ a)).card = ∑ o ∈ F, (o ∩ a).card :=
        Finset.card_biUnion hpd
  4. The union ⋃_{o ∈ F} (o ∩ a) is a subset of a, so its cardinality is at most |a|.

    Every element x in the union belongs to o ∩ a for some o ∈ F (`Finset.mem_biUnion`), hence x ∈ a by `Finset.mem_inter.mp`. Because the union is a subset of a, its cardinality cannot exceed |a| (`Finset.card_le_card`).

    lines 17–22

    uses Finset.mem_biUnion, Finset.mem_inter.mp, Finset.card_le_card

      have hsub : F.biUnion (fun o => o ∩ a) ⊆ a := by
        intro x hx
        rw [Finset.mem_biUnion] at hx
        obtain ⟨o, ho, hxo⟩ := hx
        exact (Finset.mem_inter.mp hxo).2
      have hle : (F.biUnion (fun o => o ∩ a)).card ≤ a.card := Finset.card_le_card hsub
  5. Each intersection o ∩ a has size at least 1 for o ∈ F.

    For o ∈ F, the sets a and o are not disjoint, so there exists an element x common to both (`Finset.not_disjoint_iff.mp`). Then x ∈ o ∩ a (`Finset.mem_inter.mpr`), which means o ∩ a is nonempty and therefore has cardinality at least 1 (`Finset.card_pos.mpr`).

    lines 23–27

    uses Finset.not_disjoint_iff.mp, Finset.card_pos.mpr, Finset.mem_inter.mpr

      have hnonempty : ∀ o ∈ F, 1 ≤ (o ∩ a).card := by
        intro o ho
        have hnd : ¬ Disjoint a o := (hmem o).mp ho |>.2
        obtain ⟨x, hxa, hxo⟩ := Finset.not_disjoint_iff.mp hnd
        exact Finset.card_pos.mpr ⟨x, Finset.mem_inter.mpr ⟨hxo, hxa⟩⟩
  6. The number of sets in O conflicting with a is at most |a|.

    The cardinality |F| equals ∑_{o ∈ F} 1 (`Finset.card_eq_sum_ones`). Since each term satisfies 1 ≤ |o ∩ a|, this sum is at most ∑_{o ∈ F} |o ∩ a| (`Finset.sum_le_sum`). In turn, this sum equals |⋃_{o ∈ F} (o ∩ a)| by disjointness, which is bounded above by |a| because the union is a subset of a.

    lines 28–31

    uses Finset.card_eq_sum_ones, Finset.sum_le_sum

      calc F.card = ∑ o ∈ F, 1 := Finset.card_eq_sum_ones F
        _ ≤ ∑ o ∈ F, (o ∩ a).card := Finset.sum_le_sum hnonempty
        _ = (F.biUnion (fun o => o ∩ a)).card := hcard.symm
        _ ≤ a.card := hle
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the original set and satisfies the predicate.
Disjoint.mono
Disjointness is monotonic: if b and d are disjoint, any subsets a ⊆ b and c ⊆ d are also disjoint.
Finset.inter_subset_left
The intersection s₁ ∩ s₂ is a subset of s₁.
Finset.card_biUnion
For a pairwise disjoint family of finite sets, the cardinality of their union is the sum of their individual cardinalities.
Finset.mem_biUnion
An element belongs to a union of sets ⋃_{a ∈ s} t(a) if and only if it belongs to t(a) for some a ∈ s.
Finset.mem_inter.mp
If an element belongs to an intersection s ∩ t, then it belongs to s and to t.
Finset.card_le_card
If s ⊆ t, then |s| ≤ |t|.
Finset.not_disjoint_iff.mp
Two sets are not disjoint if and only if they share at least one common element.
Finset.card_pos.mpr
A finite set has strictly positive cardinality (at least 1) if and only if it is nonempty.
Finset.mem_inter.mpr
If an element belongs to both s and t, then it belongs to s ∩ t.
Finset.card_eq_sum_ones
The cardinality of a finite set is equal to the sum of 1 over all of its elements.
Finset.sum_le_sum
If f(i) ≤ g(i) for all i ∈ s, then the sum of f over s is at most the sum of g over s.

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

/-- Degree bound: a single set intersects at most |a| members of a packing. -/theorem op_98_conflict_degree_bound {α : Type*} [DecidableEq α] {k : ℕ}    (inst : WeightedSetPackingInstance α k) (O : Finset (Finset α)) (a : Finset α)    (hO : is_packing inst O) :    (O.filter (fun o => ¬ Disjoint a o)).card ≤ a.card := by  set F := O.filter (fun o => ¬ Disjoint a o) with hF  have hmem : ∀ o, o ∈ F ↔ o ∈ O ∧ ¬ Disjoint a o := by    intro o; rw [hF, Finset.mem_filter]  have hpd : (F : Set (Finset α)).PairwiseDisjoint (fun o => o ∩ a) := by    intro o ho o' ho' hne    have hoO : o ∈ O := (hmem o).mp ho |>.1    have ho'O : o' ∈ O := (hmem o').mp ho' |>.1    exact Disjoint.mono Finset.inter_subset_left Finset.inter_subset_left      (hO.2 hoO ho'O hne)  have hcard : (F.biUnion (fun o => o ∩ a)).card = ∑ o ∈ F, (o ∩ a).card :=    Finset.card_biUnion hpd  have hsub : F.biUnion (fun o => o ∩ a) ⊆ a := by    intro x hx    rw [Finset.mem_biUnion] at hx    obtain ⟨o, ho, hxo⟩ := hx    exact (Finset.mem_inter.mp hxo).2  have hle : (F.biUnion (fun o => o ∩ a)).card ≤ a.card := Finset.card_le_card hsub  have hnonempty : ∀ o ∈ F, 1 ≤ (o ∩ a).card := by    intro o ho    have hnd : ¬ Disjoint a o := (hmem o).mp ho |>.2    obtain ⟨x, hxa, hxo⟩ := Finset.not_disjoint_iff.mp hnd    exact Finset.card_pos.mpr ⟨x, Finset.mem_inter.mpr ⟨hxo, hxa⟩⟩  calc F.card = ∑ o ∈ F, 1 := Finset.card_eq_sum_ones F    _ ≤ ∑ o ∈ F, (o ∩ a).card := Finset.sum_le_sum hnonempty    _ = (F.biUnion (fun o => o ∩ a)).card := hcard.symm    _ ≤ a.card := hle
See it in the graphDiscuss this resultChallenge it