AFTD Auto-Formalizing Theoretical Domains

WeightedSetPackingInstance

structure

For a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists of a finite set family : Finset (Finset α) of nonempty finite subsets of α of cardinality at most k, and a weight function weight : Finset α → ℚ assigning strictly positive rational weight to every set in family.

Statement

structure WeightedSetPackingInstance (α : Type*) [DecidableEq α] (k : ℕ)
Defined in
arXiv:2610.10036 Sec. 3
Verified
19 Oct 2026
Axioms
none listed
Used by 17
  • op_98_no_singleton_repairUnder square local optimality a single-set exchange never has positive linear gain: for X = {s}, w(s)² ≤ squared_weight(N(A,{s})) ≤…
  • 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…
  • 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…
  • 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,…
  • squared_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the squared-weight potential squared_weight inst A…
  • apply_repairs_is_packingIn a weighted k-set packing instance inst over α with decidable equality, applying a compatible family of repairs R whose sets belong to…
  • 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…
  • 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…
  • packing_weightGiven an instance inst of weighted k-set packing on a type α with decidable equality, the linear weight packing_weight inst A of 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…
  • claws_from_packing_compatibleIn a weighted k-set packing instance inst over α with decidable equality, any collection of repairs R : Finset (Finset (Finset α)) whose…
  • is_repairGiven an instance inst of weighted k-set packing on a type α with decidable equality, a sub-collection X : Finset (Finset α) is a repair…
  • 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…
  • 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.
  • 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…

Read back from the Lean

A structure WeightedSetPackingInstance parameterized by a type α with decidable equality and a natural number k, containing: 1. family: a finite set of finite subsets of α (Finset (Finset α)). 2. card_le: a proof that for every set s ∈ family, the cardinality of s is at most k (Finset.card s ≤ k). 3. nonempty: a proof that for every set s ∈ family, s is nonempty (Finset.Nonempty s, i.e. ∃ x, x ∈ s). 4. weight: a function assigning a rational number to each finite subset of α (Finset α → ℚ). 5. weight_pos: a proof that for every set s ∈ family, its weight is strictly positive (0 < weight s).

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

/-- An instance of Maximum Weighted k-Set Packing over a universe α. -/
structure WeightedSetPackingInstance (α : Type*) [DecidableEq α] (k : ℕ) where
  family : Finset (Finset α)
  card_le : ∀ s ∈ family, s.card ≤ k
  nonempty : ∀ s ∈ family, s.Nonempty
  weight : Finset α → ℚ
  weight_pos : ∀ s ∈ family, 0 < weight s
See it in the graphDiscuss this resultChallenge it