AFTD Auto-Formalizing Theoretical Domains

packing_weight

def

Given an instance inst of weighted k-set packing on a type α with decidable equality, the linear weight packing_weight inst A of a sub-collection A : Finset (Finset α) is the sum of inst.weight s over all s ∈ A.

Statement

def packing_weight {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A : Finset (Finset α)) : ℚ
Defined in
arXiv:2610.10036 Sec. 3
Verified
19 Oct 2026
Axioms
none listed
Built on 1
  • WeightedSetPackingInstanceFor a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists of a…
Used by 7
  • 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_small_packing_boundSpecial case of the target: when the competing packing has at most 4 sets, weight(O) ≤ 2·weight(A), so c = 2 with the empty repair family…
  • op_98_sum_conflict_neighborhood_weightThe sum of conflict neighborhood weights over a packing O equals the weighted sum of conflict degrees in O over A: ∑_{o ∈ O} weight(N(A,…
  • 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_sq_exchange_boundObjective switching, first half: square local optimality turns the squared potential inequality for exchanges of at most 4 sets into a…
  • linear_gainGiven an instance inst of weighted k-set packing on a type α with decidable equality, the linear gain linear_gain inst A X of an exchange…
  • 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.

Read back from the Lean

Given a type α with decidable equality, an implicit natural number k, a weighted set packing instance inst on α with parameter k, and a finite set A of finite subsets of α, packing_weight inst A is defined as the rational sum of inst.weight s over all sets s ∈ A.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Linear weight of a subfamily of sets. -/
def packing_weight {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A : Finset (Finset α)) : ℚ := ∑ s ∈ A, inst.weight s
See it in the graphDiscuss this resultChallenge it