finite_three_set_stable_maximum_packings_cover_support
For a finite family of three-element sets, suppose every packing has at most k members and, for each point occurring in the family, some k-member packing omits that point. Then every point occurring in the family is covered by some k-member packing.
Statement
theorem finite_three_set_stable_maximum_packings_cover_support {α : 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 : ∀ y ∈ F.biUnion id, ∃ P : Finset (Finset α), P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧ ∀ s ∈ P, y ∉ s) : ∀ x ∈ F.biUnion id, ∃ P : Finset (Finset α), P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧ ∃ s ∈ P, x ∈ s
- Source
- Elementary packing exchange for the triangle packing-cover campaign, related to arXiv:2610.15539, Section 1.
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 3
- finite_three_set_stable_nonextendable_triple_patternsIn a finite family of three-element sets where every point can be omitted by some maximum packing, if a triple belongs to no maximum…
- finite_three_set_stable_small_cover_supported_by_two_maximum_packingsFor a stable finite three-set family with packing number k, any cover of size at most k+1 using only active points is contained in the…
- simple_graph_stable_triangle_active_edge_in_maximum_packingIn a finite graph where deleting any edge preserves the maximum triangle packing number, every edge belonging to a triangle is used by…
The proof, explained
The proof proceeds by contradiction: suppose an element x in the support of F is not covered by any maximum packing (a packing of size k). Choosing a 3-element set T = {x, y, z} in F containing x, the stability assumption gives a maximum packing P avoiding y, which by hypothesis must also avoid x. If no block of P contained z, adjoining T to P would create a packing of size k + 1, contradicting the maximum packing size k. Therefore, exactly one block r in P contains z; replacing r with T produces a valid packing of size k that covers x, providing the desired contradiction.
There is a 3-element set T = {x, y, z} in F containing x with y ≠ z.
Let x be an element in the support of F (that is, x ∈ ⋃ F). By definition of the union, x ∈ T for some T ∈ F. Since every set in F has cardinality 3, removing x leaves a 2-element set T \ {x} = {y, z} with y ≠ z. Reinserting x gives T = {x, y, z}, so y ∈ T and z ∈ T as well.
uses
Finset.mem_biUnion.mp,Finset.card_erase_of_mem,Finset.card_eq_two.mp,Finset.insert_eraseclassical intro x hx obtain ⟨T, hTF, hxT⟩ := Finset.mem_biUnion.mp hx change x ∈ T at hxT have herase : (T.erase x).card = 2 := by rw [Finset.card_erase_of_mem hxT, hthree T hTF] obtain ⟨y, z, hyz, hyzT⟩ := Finset.card_eq_two.mp herase have hTx : T = {x, y, z} := by have hh := Finset.insert_erase hxT rw [hyzT] at hh simpa using hh.symm have hyT : y ∈ T := by rw [hTx]; simp have hzT : z ∈ T := by rw [hTx]; simp
Assuming no k-member packing covers x, there is a k-member packing P ⊆ F avoiding both x and y.
We proceed by contradiction: assume no pairwise disjoint family of k sets in F covers x. Since y ∈ T ∈ F, y is in the support of F. By the stability hypothesis (`hstable`), there is a packing P ⊆ F of size k avoiding y. By the contradiction assumption, P cannot cover x either, so every set s ∈ P avoids both x and y.
uses
Finset.mem_biUnion.mprby_contra hfail have hyF : y ∈ F.biUnion id := Finset.mem_biUnion.mpr ⟨T, hTF, hyT⟩ obtain ⟨P, hPF, hPd, hPk, hPy⟩ := hstable y hyF have hPx : ∀ s ∈ P, x ∉ s := by intro s hs hxs exact hfail ⟨P, hPF, hPd, hPk, s, hs, hxs⟩
Any set s ∈ P not containing z is disjoint from T.
Since T = {x, y, z}, any element in T ∩ s must be x, y, or z. But no s ∈ P contains x (by the contradiction hypothesis) or y (by the choice of P). Thus, if z ∉ s, s contains none of the elements of T, so T and s are disjoint.
uses
Finset.disjoint_left.mpr,Finset.mem_insert,Finset.mem_singletonhave hdisT : ∀ s ∈ P, z ∉ s → Disjoint T s := by intro s hs hzs apply Finset.disjoint_left.mpr intro a ha has rw [hTx] at ha simp only [Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl | rfl · exact hPx s hs has · exact hPy s hs has · exact hzs has
Some member r ∈ P contains z.
Suppose, for contradiction, that no member of P contains z. Then by the previous step, T is disjoint from every member of P. Moreover, T ∉ P because x ∈ T while all members of P avoid x. Thus P ∪ {T} would be a pairwise disjoint subfamily of F of size |P| + 1 = k + 1. But the maximality hypothesis (`hmax`) asserts that any packing in F has size at most k, which would force k + 1 ≤ k. This contradiction shows that some r ∈ P must contain z.
uses
Finset.mem_insert.mp,Finset.mem_coe,Finset.mem_insert,Finset.card_insert_of_notMemhave hrex : ∃ r ∈ P, z ∈ r := by by_contra hno have hnoz : ∀ s ∈ P, z ∉ s := by simpa using hno have hnot : T ∉ P := by intro hTP exact hPx T hTP hxT have hsub : insert T P ⊆ F := by intro s hs rcases Finset.mem_insert.mp hs with rfl | hs · exact hTF · exact hPF hs have hpair : ((insert T P : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by intro s hs t ht hne simp only [Finset.mem_coe, Finset.mem_insert] at hs ht rcases hs with rfl | hs <;> rcases ht with rfl | ht · exact (hne rfl).elim · exact hdisT t ht (hnoz t ht) · exact (hdisT s hs (hnoz s hs)).symm · exact hPd hs ht hne have hc := hmax (insert T P) hsub hpair rw [Finset.card_insert_of_notMem hnot, hPk] at hc omega obtain ⟨r, hrP, hzr⟩ := hrex
T ∉ P, and T is disjoint from every set in P \ {r}.
First, T ∉ P because x ∈ T and no set in P contains x. Second, the sets in P are pairwise disjoint. Since z ∈ r, no other set s ∈ P \ {r} can contain z. By the disjointness property established earlier, every such s is disjoint from T.
uses
Finset.mem_erase.mp,Finset.disjoint_left.mphave hnot : T ∉ P := by intro hTP exact hPx T hTP hxT have hrest : ∀ s ∈ P.erase r, Disjoint T s := by intro s hs have hsP := (Finset.mem_erase.mp hs).2 have hsr := (Finset.mem_erase.mp hs).1 apply hdisT s hsP intro hzs have hd := hPd hsP hrP hsr exact (Finset.disjoint_left.mp hd) hzs hzr
Replacing r with T in P gives a k-member packing covering x, reaching a contradiction.
Define Q = (P \ {r}) ∪ {T}. Since T ∈ F and P ⊆ F, we have Q ⊆ F. The family Q is pairwise disjoint because P \ {r} is pairwise disjoint and T is disjoint from every member of P \ {r}. Since r ∈ P and T ∉ P, we have |Q| = |P| - 1 + 1 = k (with k > 0 because r ∈ P). Thus Q is a k-member packing covering x (via T ∈ Q and x ∈ T), contradicting the assumption that no such packing exists.
uses
Finset.mem_insert,Finset.mem_erase,Finset.mem_coe,Finset.mem_erase.mpr,Finset.card_insert_of_notMem,Finset.mem_of_mem_erase,Finset.card_erase_of_mem,Finset.card_pos.mpr,Finset.mem_insert_selflet Q : Finset (Finset α) := insert T (P.erase r) have hQF : Q ⊆ F := by intro s hs simp only [Q, Finset.mem_insert, Finset.mem_erase] at hs rcases hs with rfl | ⟨_, hs⟩ · exact hTF · exact hPF hs have hQd : (Q : Set (Finset α)).Pairwise Disjoint := by intro s hs t ht hne simp only [Q, Finset.mem_coe, Finset.mem_insert, Finset.mem_erase] at hs ht rcases hs with rfl | ⟨hsr, hs⟩ <;> rcases ht with rfl | ⟨htr, ht⟩ · exact (hne rfl).elim · exact hrest t (Finset.mem_erase.mpr ⟨htr, ht⟩) · exact (hrest s (Finset.mem_erase.mpr ⟨hsr, hs⟩)).symm · exact hPd hs ht hne have hQk : Q.card = k := by change (insert T (P.erase r)).card = k rw [Finset.card_insert_of_notMem (fun h => hnot (Finset.mem_of_mem_erase h)), Finset.card_erase_of_mem hrP, hPk] have : 0 < k := by rw [← hPk]; exact Finset.card_pos.mpr ⟨r, hrP⟩ omega exact hfail ⟨Q, hQF, hQd, hQk, T, Finset.mem_insert_self _ _, hxT⟩
Finset.mem_biUnion.mp- An element belongs to an indexed union of finsets if and only if it belongs to one of the component finsets.
Finset.mem_biUnion.mpr- If an element belongs to a component finset of an indexed union, it belongs to the union.
Finset.card_erase_of_mem- Removing an element from a finset containing it decreases its cardinality by 1.
Finset.card_eq_two.mp- A finset has cardinality 2 if and only if it consists of two distinct elements.
Finset.insert_erase- Reinserting an element into a finset from which it was removed restores the original finset.
Finset.disjoint_left.mpr- Two finsets are disjoint if no element of the first belongs to the second.
Finset.disjoint_left.mp- If two finsets are disjoint, no element of the first belongs to the second.
Finset.mem_insert- An element belongs to `insert b s` if and only if it equals b or belongs to s.
Finset.mem_insert.mp- If an element belongs to `insert b s`, it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton `{a}` if and only if it equals a.
Finset.mem_coe- Membership in a finset is equivalent to membership in its coercion to a set.
Finset.card_insert_of_notMem- Inserting an element not already in a finset increases its cardinality by 1.
Finset.mem_erase.mp- If an element belongs to `s.erase a`, it belongs to s and is distinct from a.
Finset.mem_erase- An element belongs to `s.erase a` if and only if it is distinct from a and belongs to s.
Finset.mem_erase.mpr- If an element is distinct from a and belongs to s, it belongs to `s.erase a`.
Finset.mem_of_mem_erase- Any element of `s.erase a` belongs to s.
Finset.card_pos.mpr- A nonempty finset has strictly positive cardinality.
Finset.mem_insert_self- An element always belongs to the finset obtained by inserting it into any finset.
- The support (or ground set) of the hypergraph F, written on paper as ⋃ F, is formalized in Lean as `F.biUnion id`.
- A packing is formalized as a finset P ⊆ F whose coercion to a set satisfies `(P : Set (Finset α)).Pairwise Disjoint`.
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_maximum_packings_cover_support {α : 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 : ∀ y ∈ F.biUnion id, ∃ P : Finset (Finset α), P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧ ∀ s ∈ P, y ∉ s) : ∀ x ∈ F.biUnion id, ∃ P : Finset (Finset α), P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧ ∃ s ∈ P, x ∈ s := by classical intro x hx obtain ⟨T, hTF, hxT⟩ := Finset.mem_biUnion.mp hx change x ∈ T at hxT have herase : (T.erase x).card = 2 := by rw [Finset.card_erase_of_mem hxT, hthree T hTF] obtain ⟨y, z, hyz, hyzT⟩ := Finset.card_eq_two.mp herase have hTx : T = {x, y, z} := by have hh := Finset.insert_erase hxT rw [hyzT] at hh simpa using hh.symm have hyT : y ∈ T := by rw [hTx]; simp have hzT : z ∈ T := by rw [hTx]; simp by_contra hfail have hyF : y ∈ F.biUnion id := Finset.mem_biUnion.mpr ⟨T, hTF, hyT⟩ obtain ⟨P, hPF, hPd, hPk, hPy⟩ := hstable y hyF have hPx : ∀ s ∈ P, x ∉ s := by intro s hs hxs exact hfail ⟨P, hPF, hPd, hPk, s, hs, hxs⟩ have hdisT : ∀ s ∈ P, z ∉ s → Disjoint T s := by intro s hs hzs apply Finset.disjoint_left.mpr intro a ha has rw [hTx] at ha simp only [Finset.mem_insert, Finset.mem_singleton] at ha rcases ha with rfl | rfl | rfl · exact hPx s hs has · exact hPy s hs has · exact hzs has have hrex : ∃ r ∈ P, z ∈ r := by by_contra hno have hnoz : ∀ s ∈ P, z ∉ s := by simpa using hno have hnot : T ∉ P := by intro hTP exact hPx T hTP hxT have hsub : insert T P ⊆ F := by intro s hs rcases Finset.mem_insert.mp hs with rfl | hs · exact hTF · exact hPF hs have hpair : ((insert T P : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by intro s hs t ht hne simp only [Finset.mem_coe, Finset.mem_insert] at hs ht rcases hs with rfl | hs <;> rcases ht with rfl | ht · exact (hne rfl).elim · exact hdisT t ht (hnoz t ht) · exact (hdisT s hs (hnoz s hs)).symm · exact hPd hs ht hne have hc := hmax (insert T P) hsub hpair rw [Finset.card_insert_of_notMem hnot, hPk] at hc omega obtain ⟨r, hrP, hzr⟩ := hrex have hnot : T ∉ P := by intro hTP exact hPx T hTP hxT have hrest : ∀ s ∈ P.erase r, Disjoint T s := by intro s hs have hsP := (Finset.mem_erase.mp hs).2 have hsr := (Finset.mem_erase.mp hs).1 apply hdisT s hsP intro hzs have hd := hPd hsP hrP hsr exact (Finset.disjoint_left.mp hd) hzs hzr let Q : Finset (Finset α) := insert T (P.erase r) have hQF : Q ⊆ F := by intro s hs simp only [Q, Finset.mem_insert, Finset.mem_erase] at hs rcases hs with rfl | ⟨_, hs⟩ · exact hTF · exact hPF hs have hQd : (Q : Set (Finset α)).Pairwise Disjoint := by intro s hs t ht hne simp only [Q, Finset.mem_coe, Finset.mem_insert, Finset.mem_erase] at hs ht rcases hs with rfl | ⟨hsr, hs⟩ <;> rcases ht with rfl | ⟨htr, ht⟩ · exact (hne rfl).elim · exact hrest t (Finset.mem_erase.mpr ⟨htr, ht⟩) · exact (hrest s (Finset.mem_erase.mpr ⟨hsr, hs⟩)).symm · exact hPd hs ht hne have hQk : Q.card = k := by change (insert T (P.erase r)).card = k rw [Finset.card_insert_of_notMem (fun h => hnot (Finset.mem_of_mem_erase h)), Finset.card_erase_of_mem hrP, hPk] have : 0 < k := by rw [← hPk]; exact Finset.card_pos.mpr ⟨r, hrP⟩ omega exact hfail ⟨Q, hQF, hQd, hQk, T, Finset.mem_insert_self _ _, hxT⟩