conflict_neighborhood
def
Given a type α with decidable equality and two finite collections of finite subsets of α, A and X (both of type Finset (Finset α)), conflict_neighborhood A X is the sub-collection of sets a ∈ A that are not disjoint from some set x ∈ X.
Statement
def conflict_neighborhood {α : Type*} [DecidableEq α] (A X : Finset (Finset α)) : Finset (Finset α)
- Defined in
- arXiv:2610.10036 Sec. 3
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Used by 13
- 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…
- apply_repairs_emptyFor any type α with decidable equality and family A : Finset (Finset α), applying the empty repair family to A yields A.
- 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,…
- 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…
- 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…
- 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.
- apply_repairsGiven a type α with decidable equality, a family A : Finset (Finset α), and a collection of repairs R : Finset (Finset (Finset α)),…
Read back from the Lean
Given a type α with decidable equality and two finite sets of finite subsets of α, A and X, conflict_neighborhood A X is defined as the sub-finset of A consisting of all a ∈ A for which there exists some x ∈ X such that a and x are not disjoint (i.e., ¬ Disjoint a x).
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
/-- The conflict neighborhood of a family X in A: sets in A intersecting some set in X. -/ def conflict_neighborhood {α : Type*} [DecidableEq α] (A X : Finset (Finset α)) : Finset (Finset α) := A.filter (fun a => ∃ x ∈ X, ¬ Disjoint a x)