AFTD Auto-Formalizing Theoretical Domains

op_98_conflict_deg_le_four

theoremverified

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.

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

    lines 7–10

    uses Finset.mem_singleton, disjoint_comm

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

    line 11

    uses op_98_conflict_degree_bound

      have h1 := op_98_conflict_degree_bound inst A o hA.1
  3. The 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.

    line 12

      have h2 := inst.card_le o (hO.1 ho)
  4. 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.

    line 13

      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

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