three_set_two_star_cover_bound
Three-element sets covering outside points through either of two fixed centers cover at most twice as many points as there are sets.
Statement
theorem three_set_two_star_cover_bound {α : Type*} [DecidableEq α] (P : Finset (Finset α)) (N : Finset α) (u v : α) (hsize : ∀ t ∈ P, t.card = 3) (hN : ∀ w ∈ N, w ≠ u ∧ w ≠ v ∧ ∃ t ∈ P, w ∈ t ∧ (u ∈ t ∨ v ∈ t)) : N.card ≤ 2 * P.card
- Source
- Structural helper for the triangle packing-cover campaign; related matching-cover reductions are in https://arxiv.org/abs/2610.15269, Lemma 2.3. Finite checks and limitations are recorded in state/campaigns/triangle_reductions/high_codegree_route_in512.md.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- simple_graph_maximal_packing_common_neighbors_leIf a maximal edge-disjoint triangle packing avoids an edge, that edge has at most twice as many common neighbors as the packing has…
The proof, explained
To bound the size of N, each set t ∈ P is mapped to a subset F(t) formed by removing u (if u ∈ t) or v (if v ∈ t), and the empty set otherwise. Because every set in P has size 3 and contains at least one of u or v when covering an element of N, each F(t) has cardinality at most 2. The covering condition ensures that N ⊆ ⋃ t ∈ P, F(t), so the union bound immediately yields |N| ≤ ∑ t ∈ P, |F(t)| ≤ 2 * |P|.
Define an auxiliary function F on sets by removing u if present, or else removing v if present, and returning the empty set otherwise.
We enable classical logic and define F(t) for any finite set t: if u ∈ t, F(t) is t with u removed; otherwise, if v ∈ t, F(t) is t with v removed; otherwise, F(t) is empty.
classical let F (t : Finset α) : Finset α := if u ∈ t then t.erase u else if v ∈ t then t.erase v else ∅
For every set t ∈ P, the cardinality of F(t) is at most 2.
Let t ∈ P. By the hypothesis hsize, |t| = 3. We split into cases on whether u ∈ t and v ∈ t. If u ∈ t, removing u yields |F(t)| = 3 - 1 = 2 by Finset.card_erase_of_mem. If u ∉ t but v ∈ t, removing v likewise yields |F(t)| = 3 - 1 = 2. If neither u nor v is in t, F(t) is empty, so |F(t)| = 0 ≤ 2. In every case, |F(t)| ≤ 2.
uses
Finset.card_erase_of_memhave hF : ∀ t ∈ P, (F t).card ≤ 2 := by intro t ht by_cases hu : u ∈ t · simp [F, hu, Finset.card_erase_of_mem hu, hsize t ht] · by_cases hv : v ∈ t · simp [F, hu, hv, Finset.card_erase_of_mem hv, hsize t ht] · simp [F, hu, hv]
The set N is a subset of the union ⋃ t ∈ P, F(t).
Let w ∈ N. By hypothesis hN, w ≠ u, w ≠ v, and there exists some t ∈ P such that w ∈ t and (u ∈ t ∨ v ∈ t). By Finset.mem_biUnion.mpr, to show w belongs to the union of all F(a) for a ∈ P, it suffices to show w ∈ F(t). If u ∈ t, then F(t) = t \ {u}, which contains w since w ∈ t and w ≠ u. If instead v ∈ t, we case-split on whether u ∈ t; if u ∈ t, w ∈ t \ {u} holds as before, and if u ∉ t, then F(t) = t \ {v}, which contains w since w ∈ t and w ≠ v.
uses
Finset.mem_biUnion.mprhave hsub : N ⊆ P.biUnion F := by intro w hw obtain ⟨hwu, hwv, t, ht, hwt, hct⟩ := hN w hw apply Finset.mem_biUnion.mpr refine ⟨t, ht, ?_⟩ rcases hct with hu | hv · simp [F, hu, hwt, hwu] · by_cases hu : u ∈ t · simp [F, hu, hwt, hwu] · simp [F, hu, hv, hwt, hwv]
The cardinality of N is at most 2 * |P|.
We compute the bound via a chain of inequalities: first, |N| ≤ |⋃ t ∈ P, F(t)| by Finset.card_le_card applied to the subset inclusion N ⊆ ⋃ t ∈ P, F(t). Second, the cardinality of the union is bounded above by the sum of individual cardinalities ∑ t ∈ P, |F(t)| by subadditivity (Finset.card_biUnion_le). Third, since each |F(t)| ≤ 2, summing over t ∈ P gives at most ∑ t ∈ P, 2 by Finset.sum_le_sum. Finally, summing the constant 2 over P equals |P| * 2, which equals 2 * |P| by Nat.mul_comm.
uses
Finset.card_le_card,Finset.card_biUnion_le,Finset.sum_le_sum,Nat.mul_commcalc N.card ≤ (P.biUnion F).card := Finset.card_le_card hsub _ ≤ ∑ t ∈ P, (F t).card := Finset.card_biUnion_le _ ≤ ∑ _t ∈ P, 2 := by exact Finset.sum_le_sum hF _ = 2 * P.card := by simp [Nat.mul_comm]
Finset.card_erase_of_mem- Removing an element from a finite set decreases its cardinality by 1.
Finset.mem_biUnion.mpr- An element belongs to a indexed union of sets ⋃ a ∈ s, t(a) if it belongs to t(a) for some a ∈ s.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most the other's cardinality.
Finset.card_biUnion_le- The cardinality of a union of finite sets is at most the sum of the cardinalities of the individual sets.
Finset.sum_le_sum- If a function f is pointwise bounded by g on a finite set s, then the sum of f over s is at most the sum of g over s.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
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.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem three_set_two_star_cover_bound {α : Type*} [DecidableEq α] (P : Finset (Finset α)) (N : Finset α) (u v : α) (hsize : ∀ t ∈ P, t.card = 3) (hN : ∀ w ∈ N, w ≠ u ∧ w ≠ v ∧ ∃ t ∈ P, w ∈ t ∧ (u ∈ t ∨ v ∈ t)) : N.card ≤ 2 * P.card := by classical let F (t : Finset α) : Finset α := if u ∈ t then t.erase u else if v ∈ t then t.erase v else ∅ have hF : ∀ t ∈ P, (F t).card ≤ 2 := by intro t ht by_cases hu : u ∈ t · simp [F, hu, Finset.card_erase_of_mem hu, hsize t ht] · by_cases hv : v ∈ t · simp [F, hu, hv, Finset.card_erase_of_mem hv, hsize t ht] · simp [F, hu, hv] have hsub : N ⊆ P.biUnion F := by intro w hw obtain ⟨hwu, hwv, t, ht, hwt, hct⟩ := hN w hw apply Finset.mem_biUnion.mpr refine ⟨t, ht, ?_⟩ rcases hct with hu | hv · simp [F, hu, hwt, hwu] · by_cases hu : u ∈ t · simp [F, hu, hwt, hwu] · simp [F, hu, hv, hwt, hwv] calc N.card ≤ (P.biUnion F).card := Finset.card_le_card hsub _ ≤ ∑ t ∈ P, (F t).card := Finset.card_biUnion_le _ ≤ ∑ _t ∈ P, 2 := by exact Finset.sum_le_sum hF _ = 2 * P.card := by simp [Nat.mul_comm]