finite_three_set_stable_nonextendable_triple_patterns
In a finite family of three-element sets where every point can be omitted by some maximum packing, if a triple belongs to no maximum packing, then for each of its points there is a maximum packing omitting that point and covering both of the other two.
Statement
theorem finite_three_set_stable_nonextendable_triple_patterns {α : Type*} [DecidableEq α] (F : Finset (Finset α)) (k : ℕ) (hthree : ∀ t ∈ F, t.card = 3) (hmax : ∀ P : Finset (Finset α), P ⊆ F → (P : Set (Finset α)).Pairwise Disjoint → P.card ≤ k) (hstable : ∀ x ∈ F.biUnion id, ∃ P : Finset (Finset α), P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧ ∀ s ∈ P, x ∉ s) (T : Finset α) (hTF : T ∈ F) (hnonextendable : ∀ P : Finset (Finset α), P ⊆ F → (P : Set (Finset α)).Pairwise Disjoint → P.card = k → T ∉ P) : ∀ x ∈ T, ∃ P : Finset (Finset α), P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧ (∀ s ∈ P, x ∉ s) ∧ (∀ y ∈ T, y ≠ x → ∃ s ∈ P, y ∈ s)
- Source
- Elementary packing exchange in the triangle packing-cover campaign, related to arXiv:2610.15539, Section 1.
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- finite_three_set_stable_maximum_packings_cover_supportFor a finite family of three-element sets, suppose every packing has at most k members and, for each point occurring in the family, some…
The proof, explained
Given a triple T ∈ F and a point x ∈ T, stability yields a maximum packing P of size k omitting x. To show that P covers the other two points of T, assume for contradiction that some y ∈ T \\ {x} is also omitted by all sets in P. Because any set in P intersecting T can only do so at the unique remaining point T \\ {x, y}, at most one set in P intersects T. But augmenting P by T (if no set intersects T) or replacing that single set with T (if one set intersects T) produces a packing containing T of size k + 1 or k, contradicting either the maximality of k or the assumption that T belongs to no maximum packing.
There exists a maximum packing P of size k that omits the chosen element x ∈ T.
Given x ∈ T, since T ∈ F is a 3-element set, x belongs to the union of F. By the stability hypothesis (hstable), there exists a pairwise disjoint subcollection P ⊆ F of size k that omits x. It remains to show that P covers every other element y ∈ T with y ≠ x.
uses
mem_biUnionopen Finset in intro x hxT have hTcard : T.card = 3 := hthree T hTF have hx_biUnion : x ∈ F.biUnion id := mem_biUnion.2 ⟨T, hTF, hxT⟩ obtain ⟨P, hPF, hPdisj, hPcard, hPnotx⟩ := hstable x hx_biUnion refine ⟨P, hPF, hPdisj, hPcard, hPnotx, ?_⟩
Suppose for contradiction that some other element y ∈ T \\ {x} is not covered by any set in P.
We assume the negation of the remaining claim, which provides an element y ∈ T with y ≠ x such that no set in P contains y.
by_contra! hmiss obtain ⟨y, hyT, hyne, hPnoty⟩ := hmissAt most one set in P intersects T.
Let C be the subcollection of sets in P that intersect T. For any two sets a, b ∈ C, their intersections with T are nonempty. Any element za ∈ a ∩ T cannot be x (since P omits x) and cannot be y (by the contradiction assumption), so za ∈ T \\ {x, y}. Similarly, any zb ∈ b ∩ T belongs to T \\ {x, y}. Since |T| = 3 and x ≠ y, the difference T \\ {x, y} has cardinality 3 - 2 = 1, meaning it contains a unique element z. Thus za = zb = z, which implies z ∈ a ∩ b. Because P is pairwise disjoint, two intersecting sets must be identical, so a = b. By card_le_one_iff, |C| ≤ 1.
uses
card_le_one_iff,card_sdiff_of_subset,card_pair,card_eq_onelet C := P.filter (fun s => ¬ Disjoint s T) have hC_le_one : C.card ≤ 1 := by rw [card_le_one_iff] intro a b ha hb rw [mem_filter] at ha hb obtain ⟨haP, hadisj⟩ := ha obtain ⟨hbP, hbdisj⟩ := hb rw [disjoint_iff_inter_eq_empty] at hadisj hbdisj have ha_nonempty : (a ∩ T).Nonempty := nonempty_iff_ne_empty.mpr hadisj have hb_nonempty : (b ∩ T).Nonempty := nonempty_iff_ne_empty.mpr hbdisj obtain ⟨za, hza⟩ := ha_nonempty obtain ⟨zb, hzb⟩ := hb_nonempty rw [mem_inter] at hza hzb have hza_diff : za ∈ T \ {x, y} := by rw [mem_sdiff, mem_insert, mem_singleton, not_or] refine ⟨hza.2, ?_⟩ constructor · rintro rfl; exact hPnotx a haP hza.1 · rintro rfl; exact hPnoty a haP hza.1 have hzb_diff : zb ∈ T \ {x, y} := by rw [mem_sdiff, mem_insert, mem_singleton, not_or] refine ⟨hzb.2, ?_⟩ constructor · rintro rfl; exact hPnotx b hbP hzb.1 · rintro rfl; exact hPnoty b hbP hzb.1 have hsub : ({x, y} : Finset α) ⊆ T := by rw [insert_subset_iff, singleton_subset_iff] exact ⟨hxT, hyT⟩ have hcard_diff : (T \ {x, y}).card = 1 := by rw [card_sdiff_of_subset hsub] have hxy_card : ({x, y} : Finset α).card = 2 := card_pair hyne.symm rw [hxy_card, hTcard] obtain ⟨z, hz⟩ := card_eq_one.mp hcard_diff have hza_z : za = z := by have := hza_diff rw [hz, mem_singleton] at this exact this have hzb_z : zb = z := by have := hzb_diff rw [hz, mem_singleton] at this exact this have h_eq : za = zb := hza_z.trans hzb_z.symm by_contra hab have hdisj : Disjoint a b := hPdisj haP hbP hab have h_inter : za ∈ a ∩ b := mem_inter.mpr ⟨hza.1, h_eq ▸ hzb.1⟩ rw [disjoint_iff_inter_eq_empty] at hdisj rw [hdisj] at h_inter exact notMem_empty za h_inter
The case |C| = 0 (no set in P intersects T) is impossible.
If |C| = 0, then C = ∅, so every set in P is disjoint from T. Furthermore, T ∉ P because T is nonempty and thus intersects itself. Adding T to P yields a pairwise disjoint subcollection P ∪ {T} ⊆ F of size k + 1. This contradicts the hypothesis (hmax) that every packing in F has size at most k.
uses
Nat.le_one_iff_eq_zero_or_eq_one,card_eq_zero,card_insert_of_notMem,Set.pairwise_insert_of_symm,Nat.not_succ_le_selfrcases Nat.le_one_iff_eq_zero_or_eq_one.mp hC_le_one with hC0 | hC1 · have hCempty : C = ∅ := card_eq_zero.mp hC0 have hTnotP : T ∉ P := by intro hTP have hCmem : T ∈ C := by rw [mem_filter] refine ⟨hTP, ?_⟩ rw [disjoint_iff_inter_eq_empty, inter_self] intro hTempty rw [hTempty] at hTcard contradiction rw [hCempty] at hCmem exact notMem_empty T hCmem have hP'disj : ((insert T P : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by rw [coe_insert, Set.pairwise_insert_of_symm] refine ⟨hPdisj, ?_⟩ intro b hb _ have hbP : b ∈ P := hb have hbnotC : b ∉ C := by rw [hCempty]; exact notMem_empty b rw [mem_filter, not_and] at hbnotC have := hbnotC hbP have hdisj : Disjoint b T := not_not.mp this exact hdisj.symm have hP'sub : insert T P ⊆ F := insert_subset hTF hPF have hP'card : (insert T P).card = k + 1 := by rw [card_insert_of_notMem hTnotP, hPcard] have hle := hmax (insert T P) hP'sub hP'disj rw [hP'card] at hle exact Nat.not_succ_le_self k hle
The case |C| = 1 (exactly one set in P intersects T) is also impossible, completing the contradiction.
If |C| = 1, then C = {s0} for some s0 ∈ P. Replacing s0 with T gives the family P' = (P \\ {s0}) ∪ {T}. Since s0 was the unique set in P intersecting T, all remaining sets in P are disjoint from T, making P' pairwise disjoint. Because s0 ∈ P and T ∉ P \\ {s0}, the size of P' is (k - 1) + 1 = k. Thus P' is a maximum packing of size k in F containing T, contradicting the assumption (hnonextendable) that T belongs to no maximum packing.
uses
card_eq_one,Set.pairwise_insert_of_symm,card_insert_of_notMem,card_sdiff_of_subset,card_singleton,Nat.sub_add_cancel,mem_insert_self· obtain ⟨s0, hs0⟩ := card_eq_one.mp hC1 have hs0C : s0 ∈ C := by rw [hs0, mem_singleton] rw [mem_filter] at hs0C have hs0P : s0 ∈ P := hs0C.1 have hTnot : T ∉ P \ {s0} := by intro hTin rw [mem_sdiff, mem_singleton] at hTin have hTC : T ∈ C := by rw [mem_filter] refine ⟨hTin.1, ?_⟩ rw [disjoint_iff_inter_eq_empty, inter_self] intro hTempty rw [hTempty] at hTcard contradiction rw [hs0, mem_singleton] at hTC exact hTin.2 hTC have hP'disj : ((insert T (P \ {s0}) : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by rw [coe_insert, Set.pairwise_insert_of_symm] refine ⟨hPdisj.mono (by rw [coe_sdiff, coe_singleton]; exact Set.sdiff_subset), ?_⟩ intro b hb _ rw [mem_coe, mem_sdiff, mem_singleton] at hb have hbP : b ∈ P := hb.1 have hbne : b ≠ s0 := hb.2 have hbnotC : b ∉ C := by rw [hs0, mem_singleton]; exact hbne rw [mem_filter, not_and] at hbnotC have := hbnotC hbP have hdisj : Disjoint b T := not_not.mp this exact hdisj.symm have hP'card : (insert T (P \ {s0})).card = k := by rw [card_insert_of_notMem hTnot] rw [card_sdiff_of_subset (singleton_subset_iff.mpr hs0P), card_singleton] rw [hPcard] have hk : 1 ≤ k := by have : 1 ≤ P.card := card_pos.mpr ⟨s0, hs0P⟩ rwa [hPcard] at this exact Nat.sub_add_cancel hk have hP'sub : insert T (P \ {s0}) ⊆ F := insert_subset hTF (sdiff_subset.trans hPF) have hTinP' : T ∈ insert T (P \ {s0}) := mem_insert_self T _ exact hnonextendable (insert T (P \ {s0})) hP'sub hP'disj hP'card hTinP'
mem_biUnion- An element belongs to the union of a family of sets if and only if it belongs to at least one set in the family.
card_le_one_iff- A finite set has at most one element if and only if any two of its elements are equal.
card_sdiff_of_subset- If s is a subset of t, then the cardinality of t \\ s equals the cardinality of t minus the cardinality of s.
card_pair- The cardinality of a pair {a, b} is 2 whenever a ≠ b.
card_eq_one- A finite set has cardinality 1 if and only if it is a singleton set.
Nat.le_one_iff_eq_zero_or_eq_one- A natural number is at most 1 if and only if it is equal to 0 or equal to 1.
card_eq_zero- A finite set has cardinality 0 if and only if it is empty.
card_insert_of_notMem- Inserting an element not already in a finite set increases the set's cardinality by 1.
Set.pairwise_insert_of_symm- For a symmetric relation, inserting an element into a pairwise-related set yields a pairwise-related set if and only if the original set was pairwise-related and the new element is related to all elements in the set.
Nat.not_succ_le_self- No natural number has its successor less than or equal to itself (that is, ¬(n + 1 ≤ n)).
card_singleton- The cardinality of any singleton set {a} is 1.
Nat.sub_add_cancel- For natural numbers with m ≤ n, subtracting m and then adding m yields n.
mem_insert_self- An element is always a member of the set obtained by inserting it into any set.
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_three_set_stable_nonextendable_triple_patterns {α : Type*} [DecidableEq α] (F : Finset (Finset α)) (k : ℕ) (hthree : ∀ t ∈ F, t.card = 3) (hmax : ∀ P : Finset (Finset α), P ⊆ F → (P : Set (Finset α)).Pairwise Disjoint → P.card ≤ k) (hstable : ∀ x ∈ F.biUnion id, ∃ P : Finset (Finset α), P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧ ∀ s ∈ P, x ∉ s) (T : Finset α) (hTF : T ∈ F) (hnonextendable : ∀ P : Finset (Finset α), P ⊆ F → (P : Set (Finset α)).Pairwise Disjoint → P.card = k → T ∉ P) : ∀ x ∈ T, ∃ P : Finset (Finset α), P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧ (∀ s ∈ P, x ∉ s) ∧ (∀ y ∈ T, y ≠ x → ∃ s ∈ P, y ∈ s) := by open Finset in intro x hxT have hTcard : T.card = 3 := hthree T hTF have hx_biUnion : x ∈ F.biUnion id := mem_biUnion.2 ⟨T, hTF, hxT⟩ obtain ⟨P, hPF, hPdisj, hPcard, hPnotx⟩ := hstable x hx_biUnion refine ⟨P, hPF, hPdisj, hPcard, hPnotx, ?_⟩ by_contra! hmiss obtain ⟨y, hyT, hyne, hPnoty⟩ := hmiss let C := P.filter (fun s => ¬ Disjoint s T) have hC_le_one : C.card ≤ 1 := by rw [card_le_one_iff] intro a b ha hb rw [mem_filter] at ha hb obtain ⟨haP, hadisj⟩ := ha obtain ⟨hbP, hbdisj⟩ := hb rw [disjoint_iff_inter_eq_empty] at hadisj hbdisj have ha_nonempty : (a ∩ T).Nonempty := nonempty_iff_ne_empty.mpr hadisj have hb_nonempty : (b ∩ T).Nonempty := nonempty_iff_ne_empty.mpr hbdisj obtain ⟨za, hza⟩ := ha_nonempty obtain ⟨zb, hzb⟩ := hb_nonempty rw [mem_inter] at hza hzb have hza_diff : za ∈ T \ {x, y} := by rw [mem_sdiff, mem_insert, mem_singleton, not_or] refine ⟨hza.2, ?_⟩ constructor · rintro rfl; exact hPnotx a haP hza.1 · rintro rfl; exact hPnoty a haP hza.1 have hzb_diff : zb ∈ T \ {x, y} := by rw [mem_sdiff, mem_insert, mem_singleton, not_or] refine ⟨hzb.2, ?_⟩ constructor · rintro rfl; exact hPnotx b hbP hzb.1 · rintro rfl; exact hPnoty b hbP hzb.1 have hsub : ({x, y} : Finset α) ⊆ T := by rw [insert_subset_iff, singleton_subset_iff] exact ⟨hxT, hyT⟩ have hcard_diff : (T \ {x, y}).card = 1 := by rw [card_sdiff_of_subset hsub] have hxy_card : ({x, y} : Finset α).card = 2 := card_pair hyne.symm rw [hxy_card, hTcard] obtain ⟨z, hz⟩ := card_eq_one.mp hcard_diff have hza_z : za = z := by have := hza_diff rw [hz, mem_singleton] at this exact this have hzb_z : zb = z := by have := hzb_diff rw [hz, mem_singleton] at this exact this have h_eq : za = zb := hza_z.trans hzb_z.symm by_contra hab have hdisj : Disjoint a b := hPdisj haP hbP hab have h_inter : za ∈ a ∩ b := mem_inter.mpr ⟨hza.1, h_eq ▸ hzb.1⟩ rw [disjoint_iff_inter_eq_empty] at hdisj rw [hdisj] at h_inter exact notMem_empty za h_inter rcases Nat.le_one_iff_eq_zero_or_eq_one.mp hC_le_one with hC0 | hC1 · have hCempty : C = ∅ := card_eq_zero.mp hC0 have hTnotP : T ∉ P := by intro hTP have hCmem : T ∈ C := by rw [mem_filter] refine ⟨hTP, ?_⟩ rw [disjoint_iff_inter_eq_empty, inter_self] intro hTempty rw [hTempty] at hTcard contradiction rw [hCempty] at hCmem exact notMem_empty T hCmem have hP'disj : ((insert T P : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by rw [coe_insert, Set.pairwise_insert_of_symm] refine ⟨hPdisj, ?_⟩ intro b hb _ have hbP : b ∈ P := hb have hbnotC : b ∉ C := by rw [hCempty]; exact notMem_empty b rw [mem_filter, not_and] at hbnotC have := hbnotC hbP have hdisj : Disjoint b T := not_not.mp this exact hdisj.symm have hP'sub : insert T P ⊆ F := insert_subset hTF hPF have hP'card : (insert T P).card = k + 1 := by rw [card_insert_of_notMem hTnotP, hPcard] have hle := hmax (insert T P) hP'sub hP'disj rw [hP'card] at hle exact Nat.not_succ_le_self k hle · obtain ⟨s0, hs0⟩ := card_eq_one.mp hC1 have hs0C : s0 ∈ C := by rw [hs0, mem_singleton] rw [mem_filter] at hs0C have hs0P : s0 ∈ P := hs0C.1 have hTnot : T ∉ P \ {s0} := by intro hTin rw [mem_sdiff, mem_singleton] at hTin have hTC : T ∈ C := by rw [mem_filter] refine ⟨hTin.1, ?_⟩ rw [disjoint_iff_inter_eq_empty, inter_self] intro hTempty rw [hTempty] at hTcard contradiction rw [hs0, mem_singleton] at hTC exact hTin.2 hTC have hP'disj : ((insert T (P \ {s0}) : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by rw [coe_insert, Set.pairwise_insert_of_symm] refine ⟨hPdisj.mono (by rw [coe_sdiff, coe_singleton]; exact Set.sdiff_subset), ?_⟩ intro b hb _ rw [mem_coe, mem_sdiff, mem_singleton] at hb have hbP : b ∈ P := hb.1 have hbne : b ≠ s0 := hb.2 have hbnotC : b ∉ C := by rw [hs0, mem_singleton]; exact hbne rw [mem_filter, not_and] at hbnotC have := hbnotC hbP have hdisj : Disjoint b T := not_not.mp this exact hdisj.symm have hP'card : (insert T (P \ {s0})).card = k := by rw [card_insert_of_notMem hTnot] rw [card_sdiff_of_subset (singleton_subset_iff.mpr hs0P), card_singleton] rw [hPcard] have hk : 1 ≤ k := by have : 1 ≤ P.card := card_pos.mpr ⟨s0, hs0P⟩ rwa [hPcard] at this exact Nat.sub_add_cancel hk have hP'sub : insert T (P \ {s0}) ⊆ F := insert_subset hTF (sdiff_subset.trans hPF) have hTinP' : T ∈ insert T (P \ {s0}) := mem_insert_self T _ exact hnonextendable (insert T (P \ {s0})) hP'sub hP'disj hP'card hTinP'