op_98_conflict_degree_bound
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|.
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.
uses
Finset.mem_filterset 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]
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`).
uses
Disjoint.mono,Finset.inter_subset_lefthave 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)
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`).
uses
Finset.card_biUnionhave hcard : (F.biUnion (fun o => o ∩ a)).card = ∑ o ∈ F, (o ∩ a).card := Finset.card_biUnion hpd
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`).
uses
Finset.mem_biUnion,Finset.mem_inter.mp,Finset.card_le_cardhave 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
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`).
uses
Finset.not_disjoint_iff.mp,Finset.card_pos.mpr,Finset.mem_inter.mprhave 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⟩⟩
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.
uses
Finset.card_eq_sum_ones,Finset.sum_le_sumcalc 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
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.
/-- 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