finite_maximum_packing_extend_of_small_conflict_neighborhood
A packing W in a finite set family extends to a maximum packing if it intersects no more members of a fixed maximum packing P than W has members.
Statement
theorem finite_maximum_packing_extend_of_small_conflict_neighborhood {α : Type*} [DecidableEq α] (F P W : Finset (Finset α)) (hnonempty : ∀ t ∈ F, t.Nonempty) (hPF : P ⊆ F) (hWF : W ⊆ F) (hPdis : (P : Set (Finset α)).Pairwise Disjoint) (hWdis : (W : Set (Finset α)).Pairwise Disjoint) (hmax : ∀ Q : Finset (Finset α), Q ⊆ F → (Q : Set (Finset α)).Pairwise Disjoint → Q.card ≤ P.card) (hconf : (P.filter fun s => ¬ Disjoint s (W.biUnion id)).card ≤ W.card) : ∃ Q : Finset (Finset α), Q ⊆ F ∧ (Q : Set (Finset α)).Pairwise Disjoint ∧ Q.card = P.card ∧ W ⊆ Q
- Source
- Elementary packing exchange in the triangle packing-cover campaign, related to arXiv:2610.15539, Section 1.
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof constructs an extension Q by removing from the maximum packing P the conflict neighborhood N (the elements of P that intersect some member of W) and replacing them with W, setting Q = (P \ N) ∪ W. Because the remaining elements of P avoid the union of W, the family Q remains pairwise disjoint and contains W by construction. The condition |N| ≤ |W| guarantees that |Q| = |P| - |N| + |W| ≥ |P|, which by the maximality of P forces |Q| = |P|, proving that Q is a maximum packing extending W.
Define the conflict neighborhood N ⊆ P and candidate extension Q.
We identify N as the subcollection of sets in P that intersect the union of W, and define Q = (P \ N) ∪ W as the candidate packing extending W.
open Finset in set N := P.filter fun s => ¬ Disjoint s (W.biUnion id) set Q := (P \ N) ∪ W
Q is a subcollection of F (Q ⊆ F).
Because P ⊆ F, the difference P \ N is also a subset of F. Since both P \ N ⊆ F and W ⊆ F, their union Q = (P \ N) ∪ W is contained in F.
uses
Finset.union_subsethave hQF : Q ⊆ F := Finset.union_subset (Finset.sdiff_subset.trans hPF) hWFThe elements of Q are pairwise disjoint.
Let a and b be distinct elements of Q = (P \ N) ∪ W. If both belong to P \ N, they are disjoint because P is pairwise disjoint. If a ∈ P \ N and b ∈ W, then by definition of N, a is disjoint from the union of all sets in W, hence disjoint from b; the case where a ∈ W and b ∈ P \ N is symmetric. Finally, if both belong to W, they are disjoint because W is pairwise disjoint.
uses
Finset.disjoint_biUnion_righthave hQdis : (Q : Set (Finset α)).Pairwise Disjoint := by intro a ha b hb hab rw [Finset.mem_coe] at ha hb change a ∈ (P \ N) ∪ W at ha change b ∈ (P \ N) ∪ W at hb rw [Finset.mem_union] at ha hb rcases ha with ha | haW · rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at ha rcases hb with hb | hbW · rw [Finset.mem_sdiff] at hb exact hPdis ha.1 hb.1 hab · have hd := ha.2 ha.1 rw [Finset.disjoint_biUnion_right] at hd exact hd b hbW · rcases hb with hb | hbW · rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at hb have hd := hb.2 hb.1 rw [Finset.disjoint_biUnion_right] at hd exact (hd a haW).symm · exact hWdis haW hbW hab
The families P \ N and W are disjoint.
Suppose, for contradiction, that some set x belongs to both P \ N and W. Since x ∈ P \ N, it is disjoint from every set in W, which implies x is disjoint from itself. Therefore x must be empty, contradicting the hypothesis that every set in F is nonempty.
uses
Finset.disjoint_left,Finset.disjoint_biUnion_right,disjoint_self.mphave hdisj : Disjoint (P \ N) W := by rw [Finset.disjoint_left] intro x hx hxW rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at hx have hd := hx.2 hx.1 rw [Finset.disjoint_biUnion_right] at hd have hxx : Disjoint x x := hd x hxW have he : x = ∅ := disjoint_self.mp hxx have hne : x.Nonempty := hnonempty x (hWF hxW) exact hne.ne_empty he
Q has the same cardinality as P (|Q| = |P|).
Because Q ⊆ F is pairwise disjoint and P is a maximum packing, |Q| ≤ |P|. Conversely, because P \ N and W are disjoint families of sets, |Q| = |P \ N| + |W| = (|P| - |N|) + |W|. Since |N| ≤ |W| by hypothesis, linear arithmetic shows |Q| ≥ |P|. By antisymmetry of ≤, |Q| = |P|.
uses
Finset.card_union_of_disjoint,Finset.card_sdiff_of_subset,Finset.filter_subset,Finset.card_le_card,le_antisymmhave hQcard : Q.card = P.card := by have h1 : Q.card ≤ P.card := hmax Q hQF hQdis have h2 : Q.card = (P \ N).card + W.card := Finset.card_union_of_disjoint hdisj have h3 : (P \ N).card = P.card - N.card := Finset.card_sdiff_of_subset (Finset.filter_subset _ P) have h4 : N.card ≤ P.card := Finset.card_le_card (Finset.filter_subset _ P) have h5 : P.card ≤ Q.card := by rw [h2, h3] omega exact le_antisymm h1 h5
There exists a maximum packing extending W, witnessed by Q.
We return Q as the desired packing: it is a subcollection of F, consists of pairwise disjoint sets, has size |Q| = |P|, and contains W by definition of Q as a union with W.
uses
Finset.subset_union_rightexact ⟨Q, hQF, hQdis, hQcard, Finset.subset_union_right⟩
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to the other's.
Finset.card_sdiff_of_subset- If s is a subset of t, the cardinality of the difference t \ s is |t| - |s|.
Finset.disjoint_biUnion_right- A set is disjoint from a union of sets if and only if it is disjoint from each member of the union.
Finset.disjoint_left- Two sets are disjoint if and only if no element of the first belongs to the second.
Finset.filter_subset- Filtering a finite set by a predicate produces a subset of the original set.
Finset.subset_union_right- Every set is a subset of any union containing it.
Finset.union_subset- A union of two sets is a subset of a third set if and only if both sets are subsets of it.
disjoint_self.mp- A set disjoint from itself is empty.
le_antisymm- If a ≤ b and b ≤ a, then a = b.
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.
theorem finite_maximum_packing_extend_of_small_conflict_neighborhood {α : Type*} [DecidableEq α] (F P W : Finset (Finset α)) (hnonempty : ∀ t ∈ F, t.Nonempty) (hPF : P ⊆ F) (hWF : W ⊆ F) (hPdis : (P : Set (Finset α)).Pairwise Disjoint) (hWdis : (W : Set (Finset α)).Pairwise Disjoint) (hmax : ∀ Q : Finset (Finset α), Q ⊆ F → (Q : Set (Finset α)).Pairwise Disjoint → Q.card ≤ P.card) (hconf : (P.filter fun s => ¬ Disjoint s (W.biUnion id)).card ≤ W.card) : ∃ Q : Finset (Finset α), Q ⊆ F ∧ (Q : Set (Finset α)).Pairwise Disjoint ∧ Q.card = P.card ∧ W ⊆ Q := by open Finset in set N := P.filter fun s => ¬ Disjoint s (W.biUnion id) set Q := (P \ N) ∪ W have hQF : Q ⊆ F := Finset.union_subset (Finset.sdiff_subset.trans hPF) hWF have hQdis : (Q : Set (Finset α)).Pairwise Disjoint := by intro a ha b hb hab rw [Finset.mem_coe] at ha hb change a ∈ (P \ N) ∪ W at ha change b ∈ (P \ N) ∪ W at hb rw [Finset.mem_union] at ha hb rcases ha with ha | haW · rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at ha rcases hb with hb | hbW · rw [Finset.mem_sdiff] at hb exact hPdis ha.1 hb.1 hab · have hd := ha.2 ha.1 rw [Finset.disjoint_biUnion_right] at hd exact hd b hbW · rcases hb with hb | hbW · rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at hb have hd := hb.2 hb.1 rw [Finset.disjoint_biUnion_right] at hd exact (hd a haW).symm · exact hWdis haW hbW hab have hdisj : Disjoint (P \ N) W := by rw [Finset.disjoint_left] intro x hx hxW rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at hx have hd := hx.2 hx.1 rw [Finset.disjoint_biUnion_right] at hd have hxx : Disjoint x x := hd x hxW have he : x = ∅ := disjoint_self.mp hxx have hne : x.Nonempty := hnonempty x (hWF hxW) exact hne.ne_empty he have hQcard : Q.card = P.card := by have h1 : Q.card ≤ P.card := hmax Q hQF hQdis have h2 : Q.card = (P \ N).card + W.card := Finset.card_union_of_disjoint hdisj have h3 : (P \ N).card = P.card - N.card := Finset.card_sdiff_of_subset (Finset.filter_subset _ P) have h4 : N.card ≤ P.card := Finset.card_le_card (Finset.filter_subset _ P) have h5 : P.card ≤ Q.card := by rw [h2, h3] omega exact le_antisymm h1 h5 exact ⟨Q, hQF, hQdis, hQcard, Finset.subset_union_right⟩