three_uniform_link_four_flower_free
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.
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.
uses
Finset.mem_image,Finset.mem_filter,Finset.card_erase_of_memdsimp 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]
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.
· rintro ⟨F, hFsub, hFcard, C, hC⟩ apply hfreeThe 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.
uses
Finset.mem_image,Finset.notMem_erasehave 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
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.
uses
Finset.mem_image,Finset.mem_filter,Finset.insert_eraserefine ⟨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
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.
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]
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}.
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)
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.
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
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.
/-- 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]