AFTD Auto-Formalizing Theoretical Domains

three_uniform_link_four_flower_free

theoremverifiedformalization

For any 3-uniform 4-flower-free family S, the link of each element x (the family of pairs s \ {x} for s ∈ S containing x) is 2-uniform and 4-flower-free.

Statement

theorem three_uniform_link_four_flower_free {α : Type*} [DecidableEq α]
    (S : Finset (Finset α))
    (h3 : ∀ s ∈ S, s.card = 3)
    (hfree : ¬ ∃ F ⊆ S, F.card = 4 ∧ ∃ C, IsSunflower F C)
    (x : α) :
    let L := (S.filter (x ∈ ·)).image (·.erase x)
    (∀ e ∈ L, e.card = 2) ∧ ¬ ∃ F ⊆ L, F.card = 4 ∧ ∃ C, IsSunflower F C
Formalizes
arXiv:2611.13495, Sec. 5
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • IsSunflowerA finite family F of finite sets is a sunflower (a delta-system) with kernel C if every member of F contains C and any two distinct…

Read back from the Lean

Let α be a type with decidable equality. Let S be a finite set of finite subsets of α such that every s ∈ S has cardinality 3 (i.e., S is a 3-uniform hypergraph). Assume that S is 4-sunflower-free (there is no subcollection F ⊆ S of cardinality 4 that forms a sunflower with some core C). For any x : α, let L be the link of x in S, defined as {s \ {x} | s ∈ S, x ∈ s}. Then: 1. Every element e ∈ L has cardinality 2 (i.e., L is a 2-uniform hypergraph / simple graph); and 2. L is also 4-sunflower-free: there is no subcollection F ⊆ L of cardinality 4 that forms a sunflower with some core C.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The 2-uniformity of the link L follows immediately because each edge of L is formed by removing the element x from a 3-element set of S containing x. To prove that L is 4-flower-free, we suppose for contradiction that L contains a sunflower F of size 4 with core C. Adding x back to each petal of F yields a 4-element subfamily of S that forms a sunflower with core C ∪ {x}, contradicting the 4-flower-freeness of S.

  1. Every edge in the link L has cardinality 2.

    We unfold the definition of the link L and split the goal into the two parts of the conjunction. Any edge e ∈ L has the form s \ {x} for some s ∈ S containing x. Since every element of S has cardinality 3, removing x leaves a set of cardinality 3 - 1 = 2.

    lines 9–15

    uses Finset.mem_image, Finset.mem_filter, Finset.card_erase_of_mem

      dsimp only
      constructor
      · intro e he
        rw [Finset.mem_image] at he
        obtain ⟨s, hs, rfl⟩ := he
        rw [Finset.mem_filter] at hs
        rw [Finset.card_erase_of_mem hs.2, h3 s hs.1]
  2. To show that L contains no 4-flower, it suffices to construct a 4-flower in S from an assumed 4-flower in L.

    Assume for contradiction that L contains a 4-flower, so there is a 4-element subfamily F ⊆ L forming a sunflower with some core C. Under the hypothesis that S contains no 4-flower, it suffices to show that S contains a sunflower of cardinality 4.

    lines 16–17

      · rintro ⟨F, hFsub, hFcard, C, hC⟩
        apply hfree
  3. The vertex x does not belong to any edge in F.

    Every edge e ∈ F belongs to L, so by definition e = s \ {x} for some s ∈ S. Therefore, x cannot be an element of e.

    lines 18–24

    uses Finset.mem_image, Finset.notMem_erase

        have hxnot : ∀ e ∈ F, x ∉ e := by
          intro e he
          have heL : e ∈ (S.filter (x ∈ ·)).image (·.erase x) := hFsub he
          rw [Finset.mem_image] at heL
          obtain ⟨s, hs, hse⟩ := heL
          rw [← hse]
          exact Finset.notMem_erase x s
  4. The family F' = {e ∪ {x} | e ∈ F} is a subfamily of S.

    We choose F' = {e ∪ {x} | e ∈ F} and core C ∪ {x} as the candidate 4-flower in S. For any A ∈ F', A = e ∪ {x} for some e ∈ F ⊆ L. By definition of L, e = s \ {x} for some s ∈ S with x ∈ s. Reinserting x gives A = (s \ {x}) ∪ {x} = s ∈ S.

    lines 25–34

    uses Finset.mem_image, Finset.mem_filter, Finset.insert_erase

        refine ⟨F.image (insert x), ?_, ?_, insert x C, ?_⟩
        · intro A hA
          rw [Finset.mem_image] at hA
          obtain ⟨e, heF, rfl⟩ := hA
          have heL : e ∈ (S.filter (x ∈ ·)).image (·.erase x) := hFsub heF
          rw [Finset.mem_image] at heL
          obtain ⟨s, hs, hse⟩ := heL
          rw [Finset.mem_filter] at hs
          rw [← hse, Finset.insert_erase hs.2]
          exact hs.1
  5. The family F' has cardinality 4.

    The operation of adding x is injective on F because x ∉ e for every e ∈ F: erasing x from e ∪ {x} uniquely recovers e. Since the map is injective on F, |F'| = |F| = 4.

    lines 35–41

    uses congrArg, Finset.erase_insert, Finset.card_image_of_injOn

        · have hinj : Set.InjOn (fun e => insert x e) (F : Set (Finset α)) := by
            intro e1 he1 e2 he2 heq
            have h1 := hxnot e1 he1
            have h2 := hxnot e2 he2
            have h := congrArg (·.erase x) heq
            rwa [Finset.erase_insert h1, Finset.erase_insert h2] at h
          rw [Finset.card_image_of_injOn hinj, hFcard]
  6. Every set in F' contains the core C ∪ {x}.

    Any set in F' is of the form e ∪ {x} for some e ∈ F. Since F is a sunflower with core C, we have C ⊆ e, which implies C ∪ {x} ⊆ e ∪ {x}.

    lines 42–46

    uses Finset.mem_image, Finset.insert_subset_insert

        · constructor
          · intro A hA
            rw [Finset.mem_image] at hA
            obtain ⟨e, heF, rfl⟩ := hA
            exact Finset.insert_subset_insert x (hC.1 e heF)
  7. Any two distinct sets in F' intersect in exactly C ∪ {x}, concluding the proof.

    Let A, B ∈ F' be distinct, so A = e₁ ∪ {x} and B = e₂ ∪ {x} with e₁, e₂ ∈ F and e₁ ≠ e₂. By distributivity of union with {x} over intersection, and since e₁ ∩ e₂ = C in the sunflower F, we have A ∩ B = (e₁ ∩ e₂) ∪ {x} = C ∪ {x}. Thus F' is a 4-flower in S, contradicting the assumption that S is 4-flower-free.

    lines 47–54

    uses Finset.mem_image, Finset.insert_inter_distrib

          · intro A hA B hB hAB
            rw [Finset.mem_image] at hA hB
            obtain ⟨e1, he1, rfl⟩ := hA
            obtain ⟨e2, he2, rfl⟩ := hB
            have hne : e1 ≠ e2 := by
              intro h
              exact hAB (by rw [h])
            rw [← Finset.insert_inter_distrib, hC.2 e1 he1 e2 he2 hne]
Finset.card_image_of_injOn
If a function f is injective on a finite set s, then |f(s)| = |s|.
Finset.card_erase_of_mem
If an element a belongs to a finite set s, removing a decreases the cardinality by 1: |s \ {a}| = |s| - 1.
Finset.erase_insert
If a ∉ s, removing a from s ∪ {a} recovers s.
Finset.insert_erase
If a ∈ s, inserting a into s \ {a} recovers the set s.
Finset.insert_inter_distrib
Adding an element distributes over intersection: (s ∩ t) ∪ {a} = (s ∪ {a}) ∩ (t ∪ {a}).
Finset.insert_subset_insert
If s ⊆ t, then s ∪ {a} ⊆ t ∪ {a}.
Finset.mem_filter
An element a belongs to the filtered set {y ∈ s | p(y)} if and only if a ∈ s and p(a) holds.
Finset.mem_image
An element b belongs to the image f(s) if and only if b = f(a) for some a ∈ s.
Finset.notMem_erase
An element a is never a member of s \ {a}.
congrArg
A function applied to equal arguments yields equal results: if a₁ = a₂, then f(a₁) = f(a₂).

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

/-- The link of any vertex in a 3-uniform 4-flower-free hypergraph is 2-uniform and 4-flower-free. -/theorem three_uniform_link_four_flower_free {α : Type*} [DecidableEq α]    (S : Finset (Finset α))    (h3 : ∀ s ∈ S, s.card = 3)    (hfree : ¬ ∃ F ⊆ S, F.card = 4 ∧ ∃ C, IsSunflower F C)    (x : α) :    let L := (S.filter (x ∈ ·)).image (·.erase x)    (∀ e ∈ L, e.card = 2) ∧ ¬ ∃ F ⊆ L, F.card = 4 ∧ ∃ C, IsSunflower F C := by  dsimp only  constructor  · intro e he    rw [Finset.mem_image] at he    obtain ⟨s, hs, rfl⟩ := he    rw [Finset.mem_filter] at hs    rw [Finset.card_erase_of_mem hs.2, h3 s hs.1]  · rintro ⟨F, hFsub, hFcard, C, hC⟩    apply hfree    have hxnot : ∀ e ∈ F, x ∉ e := by      intro e he      have heL : e ∈ (S.filter (x ∈ ·)).image (·.erase x) := hFsub he      rw [Finset.mem_image] at heL      obtain ⟨s, hs, hse⟩ := heL      rw [← hse]      exact Finset.notMem_erase x s    refine ⟨F.image (insert x), ?_, ?_, insert x C, ?_⟩    · intro A hA      rw [Finset.mem_image] at hA      obtain ⟨e, heF, rfl⟩ := hA      have heL : e ∈ (S.filter (x ∈ ·)).image (·.erase x) := hFsub heF      rw [Finset.mem_image] at heL      obtain ⟨s, hs, hse⟩ := heL      rw [Finset.mem_filter] at hs      rw [← hse, Finset.insert_erase hs.2]      exact hs.1    · have hinj : Set.InjOn (fun e => insert x e) (F : Set (Finset α)) := by        intro e1 he1 e2 he2 heq        have h1 := hxnot e1 he1        have h2 := hxnot e2 he2        have h := congrArg (·.erase x) heq        rwa [Finset.erase_insert h1, Finset.erase_insert h2] at h      rw [Finset.card_image_of_injOn hinj, hFcard]    · constructor      · intro A hA        rw [Finset.mem_image] at hA        obtain ⟨e, heF, rfl⟩ := hA        exact Finset.insert_subset_insert x (hC.1 e heF)      · intro A hA B hB hAB        rw [Finset.mem_image] at hA hB        obtain ⟨e1, he1, rfl⟩ := hA        obtain ⟨e2, he2, rfl⟩ := hB        have hne : e1 ≠ e2 := by          intro h          exact hAB (by rw [h])        rw [← Finset.insert_inter_distrib, hC.2 e1 he1 e2 he2 hne]
See it in the graphDiscuss this resultChallenge it