op_98_conflict_deg_le_four
For any weighted 4-set packing instance inst and packings A, O, if A is square locally optimal and o ∈ O, then (conflict_neighborhood A {o}).card ≤ 4.
Statement
theorem op_98_conflict_deg_le_four {α : Type*} [DecidableEq α] (inst : WeightedSetPackingInstance α 4) (A O : Finset (Finset α)) (hA : is_square_locally_optimal inst 4 A) (hO : is_packing inst O) (o : Finset α) (ho : o ∈ O) : (conflict_neighborhood A {o}).card ≤ 4
- Source
- step towards op_98_repairs_free_bound
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- WeightedSetPackingInstanceFor a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists 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 α)),…
- 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…
- 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 size of the conflict neighborhood of a singleton {o} in a square locally optimal packing A, we first identify the neighborhood as the subcollection of sets in A that intersect o. Since A is a packing, its sets are pairwise disjoint, so by the conflict degree bound at most |o| sets in A can intersect o. Finally, because o belongs to a packing in a 4-set packing instance, |o| ≤ 4, which immediately yields the upper bound of 4.
The conflict neighborhood of {o} in A equals the set of elements in A intersecting o, reducing the goal to showing that this set has cardinality at most 4.
By definition, the conflict neighborhood of {o} in A consists of all sets a ∈ A that are not disjoint from some element of {o}. Using `Finset.mem_singleton` and the symmetry of disjointness (`disjoint_comm`), this simplifies to {a ∈ A | ¬ Disjoint o a}. Rewriting with this equivalence updates the goal accordingly.
uses
Finset.mem_singleton,disjoint_commhave hfs : conflict_neighborhood A {o} = A.filter (fun a => ¬ Disjoint o a) := by ext a simp [conflict_neighborhood, Finset.mem_singleton, disjoint_comm] rw [hfs]
The number of sets in A intersecting o is at most the cardinality of o.
Since A is square locally optimal, it is in particular a valid packing (hA.1). Applying `op_98_conflict_degree_bound` to the packing A and the set o shows that at most |o| sets in A can intersect o.
uses
op_98_conflict_degree_boundhave h1 := op_98_conflict_degree_bound inst A o hA.1The set o has cardinality at most 4.
Because O is a packing, all of its elements belong to the instance family (hO.1). By definition of a 4-set packing instance, every set in the family has cardinality at most 4, so |o| ≤ 4.
have h2 := inst.card_le o (hO.1 ho)The conflict neighborhood of {o} in A has cardinality at most 4. automation
Linear integer arithmetic combines the bounds |{a ∈ A | ¬ Disjoint o a}| ≤ |o| and |o| ≤ 4 to conclude that |{a ∈ A | ¬ Disjoint o a}| ≤ 4, closing the goal.
omega
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
disjoint_comm- Disjointness is symmetric: a is disjoint from b if and only if b is disjoint from a.
op_98_conflict_degree_bound- In any packing, the number of sets that intersect a given set a is at most the cardinality of a.
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.
/-- Every element o of a packing O has conflict degree at most 4 in A for a 4-set packing instance. -/theorem op_98_conflict_deg_le_four {α : Type*} [DecidableEq α] (inst : WeightedSetPackingInstance α 4) (A O : Finset (Finset α)) (hA : is_square_locally_optimal inst 4 A) (hO : is_packing inst O) (o : Finset α) (ho : o ∈ O) : (conflict_neighborhood A {o}).card ≤ 4 := by have hfs : conflict_neighborhood A {o} = A.filter (fun a => ¬ Disjoint o a) := by ext a simp [conflict_neighborhood, Finset.mem_singleton, disjoint_comm] rw [hfs] have h1 := op_98_conflict_degree_bound inst A o hA.1 have h2 := inst.card_le o (hO.1 ho) omega