AFTD Auto-Formalizing Theoretical Domains

three_set_two_star_cover_bound

theoremverified

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

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|.

  1. 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.

    lines 11–13

      classical
      let F (t : Finset α) : Finset α :=
        if u ∈ t then t.erase u else if v ∈ t then t.erase v else ∅
  2. 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.

    lines 14–20

    uses Finset.card_erase_of_mem

      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]
  3. 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.

    lines 21–30

    uses Finset.mem_biUnion.mpr

      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]
  4. 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.

    lines 31–35

    uses Finset.card_le_card, Finset.card_biUnion_le, Finset.sum_le_sum, Nat.mul_comm

      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]
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

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]
See it in the graphDiscuss this resultChallenge it