finite_three_set_private_packing_conflict_degree_le_two
For two disjoint-within-family collections of triples P and W, if C meets each P-triple and each W-triple meets C in one point outside the union of P, then each triple in either family intersects at most two triples of the other family.
Statement
theorem finite_three_set_private_packing_conflict_degree_le_two {α : Type*} [DecidableEq α] (P W : Finset (Finset α)) (C : Finset α) (hPsize : ∀ s ∈ P, s.card = 3) (hWsize : ∀ t ∈ W, t.card = 3) (hPdis : (P : Set (Finset α)).Pairwise Disjoint) (hWdis : (W : Set (Finset α)).Pairwise Disjoint) (hC : ∀ s ∈ P, ¬ Disjoint C s) (hprivate : ∀ t ∈ W, (t ∩ C).card = 1 ∧ Disjoint (t ∩ C) (P.biUnion id)) : (∀ s ∈ P, (W.filter fun t => ¬ Disjoint s t).card ≤ 2) ∧ (∀ t ∈ W, (P.filter fun s => ¬ Disjoint s t).card ≤ 2)
- Source
- Elementary incidence counting in the triangle packing-cover campaign, related to arXiv:2610.15539, Section 1.
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
To bound the number of conflicting triples between P and W by two in both directions, the proof shows that all intersections must occur outside C. For any triple s in P, any conflicting triple t in W must meet s in s \ C because the private point t ∩ C is disjoint from the union of P. Pairwise disjointness of W then allows injecting the conflicting triples into s \ C, whose size is at most 2 since s has size 3 and meets C. Symmetrically, conflicting triples in P inject into t \ C, which has size exactly 2 because |t| = 3 and |t ∩ C| = 1.
If s has size 3 and meets C, then |s \ C| ≤ 2.
Since s ∩ C ⊆ s, the cardinalities partition as |s \ C| + |s ∩ C| = |s| = 3. Because s ∩ C is nonempty, |s ∩ C| ≥ 1, so linear integer arithmetic yields |s \ C| ≤ 2.
uses
Finset.card_sdiff_add_card_eq_card,Finset.inter_subset_lefthave hcard : (s \ C).card + (s ∩ C).card = s.card := by have hh := Finset.card_sdiff_add_card_eq_card (s := s ∩ C) (t := s) Finset.inter_subset_left rw [show s \ (s ∩ C) = s \ C by ext x; simp] at hh exact hh have hpos : 0 < (s ∩ C).card := h.card_pos omega
If t has size 3 and |t ∩ C| = 1, then |t \ C| = 2.
As above, |t \ C| + |t ∩ C| = |t| = 3. Substituting |t ∩ C| = 1 immediately gives |t \ C| = 2.
uses
Finset.card_sdiff_add_card_eq_card,Finset.inter_subset_lefthave hcard : (t \ C).card + (t ∩ C).card = t.card := by have hh := Finset.card_sdiff_add_card_eq_card (s := t ∩ C) (t := t) Finset.inter_subset_left rw [show t \ (t ∩ C) = t \ C by ext x; simp] at hh exact hh omega
The choice function f maps the conflicting elements of X into z \ C.
Let D be the subcollection of sets in X that intersect z. For each t ∈ D, the hypothesis hex guarantees an element in (z \ C) ∩ t; defining f(t) by choosing such an element, f sends every t ∈ D into z \ C.
uses
Finset.filter_subset,Finset.mem_filter.mp,dif_pos,Classical.choose_specclassical let D := X.filter (fun t => ¬ Disjoint z t) have hDsub : D ⊆ X := Finset.filter_subset _ _ let f : Finset α → α := fun t => if h : ∃ x, x ∈ z \ C ∧ x ∈ t then Classical.choose h else a0 have hf_maps : Set.MapsTo f ↑D ↑(z \ C) := by intro t ht have htX : t ∈ X := hDsub ht have hconf : ¬ Disjoint z t := (Finset.mem_filter.mp ht).2 have h := hex t htX hconf have hft : f t = Classical.choose h := by dsimp [f] rw [dif_pos h] rw [hft] exact (Classical.choose_spec h).1
The map f is injective on D, so |D| ≤ |z \ C|.
If f(t₁) = f(t₂) = x, then x ∈ t₁ and x ∈ t₂. Since X is pairwise disjoint, t₁ and t₂ cannot share an element unless t₁ = t₂. Hence f is injective on D, and the cardinality of D is at most |z \ C|.
uses
Finset.filter_subset,Finset.mem_filter.mp,dif_pos,Classical.choose_spec,Finset.disjoint_left.mp,Finset.card_le_card_of_injOnhave hf_inj : Set.InjOn f ↑D := by intro t1 ht1 t2 ht2 heq by_contra hne have ht1X : t1 ∈ X := hDsub ht1 have ht2X : t2 ∈ X := hDsub ht2 have hconf1 : ¬ Disjoint z t1 := (Finset.mem_filter.mp ht1).2 have hconf2 : ¬ Disjoint z t2 := (Finset.mem_filter.mp ht2).2 have h1 := hex t1 ht1X hconf1 have h2 := hex t2 ht2X hconf2 have hf1 : f t1 = Classical.choose h1 := by dsimp [f]; rw [dif_pos h1] have hf2 : f t2 = Classical.choose h2 := by dsimp [f]; rw [dif_pos h2] have hx1 : Classical.choose h1 ∈ t1 := (Classical.choose_spec h1).2 have hx2 : Classical.choose h2 ∈ t2 := (Classical.choose_spec h2).2 have hxmem2 : Classical.choose h1 ∈ t2 := by rw [← hf1, heq, hf2] exact hx2 have hdis : Disjoint t1 t2 := hXdis ht1X ht2X hne exact (Finset.disjoint_left.mp hdis hx1 hxmem2).elim calc (X.filter (fun t => ¬ Disjoint z t)).card = D.card := rfl _ ≤ (z \ C).card := Finset.card_le_card_of_injOn f hf_maps hf_inj
For each s ∈ P, any t ∈ W intersecting s intersects s outside C.
Fix s ∈ P and suppose t ∈ W intersects s at a point x. If x were in C, then x would belong to t ∩ C, and since x ∈ s, also to the union of P. But t ∩ C is disjoint from the union of P, a contradiction. Thus x ∉ C, meaning x ∈ (s \ C) ∩ t.
uses
Finset.card_pos.mp,Finset.not_disjoint_iff_nonempty_inter.mp,Finset.mem_inter,Finset.mem_sdiff,Finset.mem_biUnion.mpr,Finset.disjoint_left.mpclassical constructor · intro s hsP let a0 : α := Classical.choose (Finset.card_pos.mp (by rw [hPsize s hsP] norm_num)) have hex : ∀ t ∈ W, ¬ Disjoint s t → ∃ x, x ∈ s \ C ∧ x ∈ t := by intro t htW hconf have hnon : (s ∩ t).Nonempty := Finset.not_disjoint_iff_nonempty_inter.mp hconf obtain ⟨x, hx⟩ := hnon rw [Finset.mem_inter] at hx refine ⟨x, ?_, hx.2⟩ rw [Finset.mem_sdiff] refine ⟨hx.1, ?_⟩ intro hxC have hxTC : x ∈ t ∩ C := by rw [Finset.mem_inter] exact ⟨hx.2, hxC⟩ have hxUnion : x ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨s, hsP, hx.1⟩ have hdis := (hprivate t htW).2 exact (Finset.disjoint_left.mp hdis hxTC hxUnion).elim
For each s ∈ P, at most 2 triples in W intersect s.
By the injection lemma with X = W and z = s, the number of triples in W intersecting s is at most |s \ C|. Since s meets C and has size 3, |s \ C| ≤ 2 by our first helper lemma, giving the upper bound 2.
uses
finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff,Finset.not_disjoint_iff_nonempty_inter.mp,Finset.inter_comm,finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_le_two,le_transhave hle := finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff a0 hWdis hex have hnonC : (s ∩ C).Nonempty := by have h := Finset.not_disjoint_iff_nonempty_inter.mp (hC s hsP) simpa [Finset.inter_comm] using h have htarget : (s \ C).card ≤ 2 := finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_le_two (hPsize s hsP) hnonC exact le_trans hle htarget
For each t ∈ W, any s ∈ P intersecting t intersects t outside C.
Fix t ∈ W and suppose s ∈ P intersects t at a point x. As before, if x ∈ C then x ∈ t ∩ C and x ∈ s ⊆ ⋃ P, contradicting the disjointness of t ∩ C and ⋃ P. Therefore x ∉ C, so x ∈ (t \ C) ∩ s.
uses
Finset.card_pos.mp,Finset.not_disjoint_iff_nonempty_inter.mp,Finset.mem_inter,Finset.mem_sdiff,Finset.mem_biUnion.mpr,Finset.disjoint_left.mp· intro t htW let a0 : α := Classical.choose (Finset.card_pos.mp (by rw [hWsize t htW] norm_num)) have hex : ∀ s ∈ P, ¬ Disjoint t s → ∃ x, x ∈ t \ C ∧ x ∈ s := by intro s hsP hconf have hnon : (t ∩ s).Nonempty := Finset.not_disjoint_iff_nonempty_inter.mp hconf obtain ⟨x, hx⟩ := hnon rw [Finset.mem_inter] at hx refine ⟨x, ?_, hx.2⟩ rw [Finset.mem_sdiff] refine ⟨hx.1, ?_⟩ intro hxC have hxTC : x ∈ t ∩ C := by rw [Finset.mem_inter] exact ⟨hx.1, hxC⟩ have hxUnion : x ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨s, hsP, hx.2⟩ have hdis := (hprivate t htW).2 exact (Finset.disjoint_left.mp hdis hxTC hxUnion).elim
For each t ∈ W, at most 2 triples in P intersect t.
By the injection lemma with X = P and z = t, the number of triples in P intersecting t is at most |t \ C|. Symmetry of disjointness allows rewriting the filter condition, and since |t| = 3 and |t ∩ C| = 1, |t \ C| = 2 by our second helper lemma. Transitivity completes the proof.
uses
finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff,Finset.filter_congr,not_congr,disjoint_comm,finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_eq_two,le_trans,le_of_eqhave hle := finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff a0 hPdis hex have hfilter : (P.filter fun s => ¬ Disjoint s t) = (P.filter fun s => ¬ Disjoint t s) := by apply Finset.filter_congr intro s hs exact not_congr (disjoint_comm (a := s) (b := t)) rw [hfilter] have htarget : (t \ C).card = 2 := finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_eq_two (hWsize t htW) (hprivate t htW).1 exact le_trans hle (le_of_eq htarget)
Finset.card_sdiff_add_card_eq_card- For finite sets s ⊆ t, |t \ s| + |s| = |t|.
Finset.inter_subset_left- For any sets s₁ and s₂, the intersection s₁ ∩ s₂ is a subset of s₁.
Finset.filter_subset- Filtering a finite set by a predicate produces a subset of the original set.
dif_pos- If a condition c is true, the dependent if-then-else evaluates to the then-branch.
Classical.choose_spec- The witness selected by Classical.choose satisfies the existence predicate.
Finset.mem_filter.mp- An element of a filtered finite set belongs to the base set and satisfies the filter condition.
Finset.disjoint_left.mp- If two sets are disjoint, any element of the first does not belong to the second.
Finset.card_le_card_of_injOn- If an injective function maps a finite set s into a finite set t, then |s| ≤ |t|.
Finset.card_pos.mp- A finite set with strictly positive cardinality is nonempty.
Finset.not_disjoint_iff_nonempty_inter.mp- If two finite sets are not disjoint, their intersection is nonempty.
Finset.mem_inter- An element belongs to the intersection of two sets if and only if it belongs to both sets.
Finset.mem_sdiff- An element belongs to the set difference s \ t if and only if it belongs to s and not to t.
Finset.mem_biUnion.mpr- An element belongs to the union of a family of sets if it belongs to at least one set in the family.
Finset.inter_comm- Intersection of finite sets is commutative.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Finset.filter_congr- If two predicates are equivalent on every element of a set, filtering by them yields identical subsets.
not_congr- Logical equivalence between two propositions implies equivalence of their negations.
disjoint_comm- Disjointness of sets is symmetric.
le_of_eq- Equality between numbers implies the corresponding non-strict inequality.
finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_le_two- A 3-element set meeting C has at most 2 elements outside C.
finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_eq_two- A 3-element set meeting C in exactly 1 element has exactly 2 elements outside C.
finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff- For a pairwise disjoint collection X, if every set in X intersecting z meets z \ C, then the number of such intersecting sets is at most |z \ C|.
- The arithmetic steps bounding the size of set differences from partition formulas (|s \ C| ≤ 2 and |t \ C| = 2) are completed using the omega decision procedure.
- To define the function choosing intersection witnesses, the proof uses Classical.choose with an arbitrary default element a0 from the nonempty base triple.
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.
private lemma finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_le_two {α : Type*} [DecidableEq α] {s C : Finset α} (hs : s.card = 3) (h : (s ∩ C).Nonempty) : (s \ C).card ≤ 2 := by have hcard : (s \ C).card + (s ∩ C).card = s.card := by have hh := Finset.card_sdiff_add_card_eq_card (s := s ∩ C) (t := s) Finset.inter_subset_left rw [show s \ (s ∩ C) = s \ C by ext x; simp] at hh exact hh have hpos : 0 < (s ∩ C).card := h.card_pos omegaprivate lemma finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_eq_two {α : Type*} [DecidableEq α] {t C : Finset α} (ht : t.card = 3) (h : (t ∩ C).card = 1) : (t \ C).card = 2 := by have hcard : (t \ C).card + (t ∩ C).card = t.card := by have hh := Finset.card_sdiff_add_card_eq_card (s := t ∩ C) (t := t) Finset.inter_subset_left rw [show t \ (t ∩ C) = t \ C by ext x; simp] at hh exact hh omegaprivate lemma finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff {α : Type*} [DecidableEq α] {X : Finset (Finset α)} {z C : Finset α} (a0 : α) (hXdis : (X : Set (Finset α)).Pairwise Disjoint) (hex : ∀ t ∈ X, ¬ Disjoint z t → ∃ x, x ∈ z \ C ∧ x ∈ t) : (X.filter (fun t => ¬ Disjoint z t)).card ≤ (z \ C).card := by classical let D := X.filter (fun t => ¬ Disjoint z t) have hDsub : D ⊆ X := Finset.filter_subset _ _ let f : Finset α → α := fun t => if h : ∃ x, x ∈ z \ C ∧ x ∈ t then Classical.choose h else a0 have hf_maps : Set.MapsTo f ↑D ↑(z \ C) := by intro t ht have htX : t ∈ X := hDsub ht have hconf : ¬ Disjoint z t := (Finset.mem_filter.mp ht).2 have h := hex t htX hconf have hft : f t = Classical.choose h := by dsimp [f] rw [dif_pos h] rw [hft] exact (Classical.choose_spec h).1 have hf_inj : Set.InjOn f ↑D := by intro t1 ht1 t2 ht2 heq by_contra hne have ht1X : t1 ∈ X := hDsub ht1 have ht2X : t2 ∈ X := hDsub ht2 have hconf1 : ¬ Disjoint z t1 := (Finset.mem_filter.mp ht1).2 have hconf2 : ¬ Disjoint z t2 := (Finset.mem_filter.mp ht2).2 have h1 := hex t1 ht1X hconf1 have h2 := hex t2 ht2X hconf2 have hf1 : f t1 = Classical.choose h1 := by dsimp [f]; rw [dif_pos h1] have hf2 : f t2 = Classical.choose h2 := by dsimp [f]; rw [dif_pos h2] have hx1 : Classical.choose h1 ∈ t1 := (Classical.choose_spec h1).2 have hx2 : Classical.choose h2 ∈ t2 := (Classical.choose_spec h2).2 have hxmem2 : Classical.choose h1 ∈ t2 := by rw [← hf1, heq, hf2] exact hx2 have hdis : Disjoint t1 t2 := hXdis ht1X ht2X hne exact (Finset.disjoint_left.mp hdis hx1 hxmem2).elim calc (X.filter (fun t => ¬ Disjoint z t)).card = D.card := rfl _ ≤ (z \ C).card := Finset.card_le_card_of_injOn f hf_maps hf_injtheorem finite_three_set_private_packing_conflict_degree_le_two {α : Type*} [DecidableEq α] (P W : Finset (Finset α)) (C : Finset α) (hPsize : ∀ s ∈ P, s.card = 3) (hWsize : ∀ t ∈ W, t.card = 3) (hPdis : (P : Set (Finset α)).Pairwise Disjoint) (hWdis : (W : Set (Finset α)).Pairwise Disjoint) (hC : ∀ s ∈ P, ¬ Disjoint C s) (hprivate : ∀ t ∈ W, (t ∩ C).card = 1 ∧ Disjoint (t ∩ C) (P.biUnion id)) : (∀ s ∈ P, (W.filter fun t => ¬ Disjoint s t).card ≤ 2) ∧ (∀ t ∈ W, (P.filter fun s => ¬ Disjoint s t).card ≤ 2) := by classical constructor · intro s hsP let a0 : α := Classical.choose (Finset.card_pos.mp (by rw [hPsize s hsP] norm_num)) have hex : ∀ t ∈ W, ¬ Disjoint s t → ∃ x, x ∈ s \ C ∧ x ∈ t := by intro t htW hconf have hnon : (s ∩ t).Nonempty := Finset.not_disjoint_iff_nonempty_inter.mp hconf obtain ⟨x, hx⟩ := hnon rw [Finset.mem_inter] at hx refine ⟨x, ?_, hx.2⟩ rw [Finset.mem_sdiff] refine ⟨hx.1, ?_⟩ intro hxC have hxTC : x ∈ t ∩ C := by rw [Finset.mem_inter] exact ⟨hx.2, hxC⟩ have hxUnion : x ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨s, hsP, hx.1⟩ have hdis := (hprivate t htW).2 exact (Finset.disjoint_left.mp hdis hxTC hxUnion).elim have hle := finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff a0 hWdis hex have hnonC : (s ∩ C).Nonempty := by have h := Finset.not_disjoint_iff_nonempty_inter.mp (hC s hsP) simpa [Finset.inter_comm] using h have htarget : (s \ C).card ≤ 2 := finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_le_two (hPsize s hsP) hnonC exact le_trans hle htarget · intro t htW let a0 : α := Classical.choose (Finset.card_pos.mp (by rw [hWsize t htW] norm_num)) have hex : ∀ s ∈ P, ¬ Disjoint t s → ∃ x, x ∈ t \ C ∧ x ∈ s := by intro s hsP hconf have hnon : (t ∩ s).Nonempty := Finset.not_disjoint_iff_nonempty_inter.mp hconf obtain ⟨x, hx⟩ := hnon rw [Finset.mem_inter] at hx refine ⟨x, ?_, hx.2⟩ rw [Finset.mem_sdiff] refine ⟨hx.1, ?_⟩ intro hxC have hxTC : x ∈ t ∩ C := by rw [Finset.mem_inter] exact ⟨hx.1, hxC⟩ have hxUnion : x ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨s, hsP, hx.2⟩ have hdis := (hprivate t htW).2 exact (Finset.disjoint_left.mp hdis hxTC hxUnion).elim have hle := finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff a0 hPdis hex have hfilter : (P.filter fun s => ¬ Disjoint s t) = (P.filter fun s => ¬ Disjoint t s) := by apply Finset.filter_congr intro s hs exact not_congr (disjoint_comm (a := s) (b := t)) rw [hfilter] have htarget : (t \ C).card = 2 := finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_eq_two (hWsize t htW) (hprivate t htW).1 exact le_trans hle (le_of_eq htarget)