fano_free_local_forbidden
In any 3-uniform Fano-free hypergraph H : Finset (Finset V), if {x, y, z} is an edge of H, then for all vertices a, b, c, d in V, the six triples {x, a, b}, {x, c, d}, {y, a, c}, {y, b, d}, {z, a, d}, and {z, b, c} cannot all belong to H.
Statement
theorem fano_free_local_forbidden {V : Type*} [DecidableEq V] (H : Finset (Finset V)) (hunif : is_three_uniform H) (hfree : is_fano_free H) (x y z a b c d : V) (hxyz : {x, y, z} ∈ H) : ¬ ({x, a, b} ∈ H ∧ {x, c, d} ∈ H ∧ {y, a, c} ∈ H ∧ {y, b, d} ∈ H ∧ {z, a, d} ∈ H ∧ {z, b, c} ∈ H)
- Formalizes
- arXiv:2610.01084 Lemma 3.1 inequality (3.1)
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_three_uniformA hypergraph F (a finite family of finite sets of vertices) is 3-uniform if every hyperedge e in F has cardinality 3.
- is_fano_freeA hypergraph H (a Finset of finite subsets of V) is Fano-free if there does not exist an embedding f : Fin 7 ↪ V such that for every…
- fano_planeThe Fano plane PG(2,2) is the 3-uniform hypergraph on Fin 7 whose hyperedges are the seven triples {0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {1, 3,…
Read back from the Lean
Let V be a type with decidable equality. Let H be a finite family of finite subsets of V (Finset (Finset V)). Assume H is 3-uniform (is_three_uniform H) and Fano-free (is_fano_free H). For any vertices x, y, z, a, b, c, d : V, if {x, y, z} ∈ H, then it is not the case that all six of {x, a, b}, {x, c, d}, {y, a, c}, {y, b, d}, {z, a, d}, and {z, b, c} are also elements of H.
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 theorem is proved by contradiction: we assume that an edge {x, y, z} and all six companion triples belong to the 3-uniform hypergraph H. By 3-uniformity, every such edge contains 3 distinct vertices, which implies that all 21 pairs formed by the seven vertices x, y, z, a, b, c, d are distinct. This pairwise distinctness ensures that the map sending the standard vertices 0, ..., 6 of the Fano plane to x, y, z, a, b, c, d is an injective embedding. Finally, we verify that the image of each of the seven lines of the Fano plane under this embedding is one of the assumed edges of H, which directly contradicts the assumption that H is Fano-free.
If {p, q, r} has cardinality 3, then p, q, and r are pairwise distinct.
We prove each of the inequalities p ≠ q, p ≠ r, and q ≠ r by contradiction. If any two vertices coincide, the set collapses to at most two elements, which has cardinality at most 2 by Finset.card_le_two. Since the cardinality is assumed to be 3, omega derives a contradiction in each case.
uses
Finset.card_le_twoprivate lemma fano_free_local_forbidden_card_three {V : Type*} [DecidableEq V] {p q r : V} (h : ({p,q,r} : Finset V).card = 3) : p ≠ q ∧ p ≠ r ∧ q ≠ r := by refine ⟨?_, ?_, ?_⟩ · intro heq have he : ({p,q,r} : Finset V) = {p,r} := by rw [heq]; simp have h1 : ({p,r} : Finset V).card = 3 := he ▸ h have h2 : ({p,r} : Finset V).card ≤ 2 := Finset.card_le_two omega · intro heq have he : ({p,q,r} : Finset V) = {q,r} := by rw [heq]; simp have h1 : ({q,r} : Finset V).card = 3 := he ▸ h have h2 : ({q,r} : Finset V).card ≤ 2 := Finset.card_le_two omega · intro heq have he : ({p,q,r} : Finset V) = {p,q} := by rw [heq]; simp have h1 : ({p,q} : Finset V).card = 3 := he ▸ h have h2 : ({p,q} : Finset V).card ≤ 2 := Finset.card_le_two omega
The map from Fin 7 to V sending 0 through 6 to x, y, z, a, b, c, d is injective when all 21 pairs among them are distinct.
Given indices i, j in Fin 7 with equal images, we perform exhaustive case analysis over all 49 pairs using fin_cases. When i = j, the indices are equal; when i ≠ j, the assumed equality of their images contradicts one of the 21 pairwise inequality hypotheses, which simp_all detects and closes using Fin.ext_iff.
uses
Fin.ext_iffprivate lemma fano_free_local_forbidden_injective {V : Type*} [DecidableEq V] (x y z a b c d : V) (hxy : x ≠ y) (hxz : x ≠ z) (hyz : y ≠ z) (hxa : x ≠ a) (hxb : x ≠ b) (hab : a ≠ b) (hxc : x ≠ c) (hxd : x ≠ d) (hcd : c ≠ d) (hya : y ≠ a) (hyc : y ≠ c) (hac : a ≠ c) (hyb : y ≠ b) (hyd : y ≠ d) (hbd : b ≠ d) (hza : z ≠ a) (hzd : z ≠ d) (had : a ≠ d) (hzb : z ≠ b) (hzc : z ≠ c) (hbc : b ≠ c) : Function.Injective (![x, y, z, a, b, c, d] : Fin 7 → V) := by intro i j hij fin_cases i <;> fin_cases j <;> simp_all [Fin.ext_iff]
Each of the seven lines of the Fano plane maps under the 7-tuple embedding to the corresponding triple in V.
For each of the seven blocks {0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {1, 3, 5}, {1, 4, 6}, {2, 3, 6}, and {2, 4, 5}, we rewrite the finset map as an image using Finset.map_eq_image and evaluate the image definitionally using Finset.image.
uses
Finset.map_eq_image,Finset.imageprivate lemma fano_free_local_forbidden_map_012 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,1,2} : Finset (Fin 7)) = ({x,y,z} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image] private lemma fano_free_local_forbidden_map_034 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,3,4} : Finset (Fin 7)) = ({x,a,b} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image] private lemma fano_free_local_forbidden_map_056 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,5,6} : Finset (Fin 7)) = ({x,c,d} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image] private lemma fano_free_local_forbidden_map_135 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({1,3,5} : Finset (Fin 7)) = ({y,a,c} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image] private lemma fano_free_local_forbidden_map_146 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({1,4,6} : Finset (Fin 7)) = ({y,b,d} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image] private lemma fano_free_local_forbidden_map_236 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({2,3,6} : Finset (Fin 7)) = ({z,a,d} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image] private lemma fano_free_local_forbidden_map_245 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({2,4,5} : Finset (Fin 7)) = ({z,b,c} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image]
Assuming the six companion triples belong to H, all 21 pairs formed by x, y, z, a, b, c, d are distinct.
We assume for contradiction that all six companion triples belong to H alongside {x, y, z}. By 3-uniformity (hunif), every edge in H has cardinality 3. Applying fano_free_local_forbidden_card_three to each of the seven edges yields that the three vertices of each edge are distinct, producing all 21 pairwise inequalities among x, y, z, a, b, c, d.
uses
fano_free_local_forbidden_card_threetheorem fano_free_local_forbidden {V : Type*} [DecidableEq V] (H : Finset (Finset V)) (hunif : is_three_uniform H) (hfree : is_fano_free H) (x y z a b c d : V) (hxyz : {x, y, z} ∈ H) : ¬ ({x, a, b} ∈ H ∧ {x, c, d} ∈ H ∧ {y, a, c} ∈ H ∧ {y, b, d} ∈ H ∧ {z, a, d} ∈ H ∧ {z, b, c} ∈ H) := by rintro ⟨hxab, hxcd, hyac, hybd, hzad, hzbc⟩ obtain ⟨hxy, hxz, hyz⟩ := fano_free_local_forbidden_card_three (hunif {x,y,z} hxyz) obtain ⟨hxa, hxb, hab⟩ := fano_free_local_forbidden_card_three (hunif {x,a,b} hxab) obtain ⟨hxc, hxd, hcd⟩ := fano_free_local_forbidden_card_three (hunif {x,c,d} hxcd) obtain ⟨hya, hyc, hac⟩ := fano_free_local_forbidden_card_three (hunif {y,a,c} hyac) obtain ⟨hyb, hyd, hbd⟩ := fano_free_local_forbidden_card_three (hunif {y,b,d} hybd) obtain ⟨hza, hzd, had⟩ := fano_free_local_forbidden_card_three (hunif {z,a,d} hzad) obtain ⟨hzb, hzc, hbc⟩ := fano_free_local_forbidden_card_three (hunif {z,b,c} hzbc)
To contradict Fano-freeness, it suffices to show that the embedding of Fin 7 defined by x, y, z, a, b, c, d maps every Fano line into H.
We invoke the Fano-free hypothesis hfree, which asserts that H contains no embedded copy of the Fano plane. It therefore suffices to exhibit an injective map from Fin 7 to V whose image on each Fano line lies in H. By fano_free_local_forbidden_injective applied to the 21 pairwise inequalities, the map sending 0 through 6 to x, y, z, a, b, c, d is injective, providing the required embedding.
uses
fano_free_local_forbidden_injectiveapply hfree have hinj : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V) := fano_free_local_forbidden_injective x y z a b c d hxy hxz hyz hxa hxb hab hxc hxd hcd hya hyc hac hyb hyd hbd hza hzd had hzb hzc hbc refine ⟨⟨![x,y,z,a,b,c,d], hinj⟩, ?_⟩
Every line of the Fano plane maps to an edge in H under the embedding, completing the contradiction.
Let e be an edge of the Fano plane. We unfold fano_plane using Finset.mem_insert and Finset.mem_singleton, splitting into seven cases. In each case, we rewrite the mapped edge using the corresponding helper lemma (fano_free_local_forbidden_map_012, fano_free_local_forbidden_map_034, fano_free_local_forbidden_map_056, fano_free_local_forbidden_map_135, fano_free_local_forbidden_map_146, fano_free_local_forbidden_map_236, fano_free_local_forbidden_map_245) to identify it with one of the seven triples, all of which are assumed to belong to H.
uses
fano_plane,Finset.mem_insert,Finset.mem_singleton,fano_free_local_forbidden_map_012,fano_free_local_forbidden_map_034,fano_free_local_forbidden_map_056,fano_free_local_forbidden_map_135,fano_free_local_forbidden_map_146,fano_free_local_forbidden_map_236,fano_free_local_forbidden_map_245intro e he simp only [fano_plane, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl | rfl | rfl | rfl | rfl · rw [fano_free_local_forbidden_map_012 x y z a b c d hinj]; exact hxyz · rw [fano_free_local_forbidden_map_034 x y z a b c d hinj]; exact hxab · rw [fano_free_local_forbidden_map_056 x y z a b c d hinj]; exact hxcd · rw [fano_free_local_forbidden_map_135 x y z a b c d hinj]; exact hyac · rw [fano_free_local_forbidden_map_146 x y z a b c d hinj]; exact hybd · rw [fano_free_local_forbidden_map_236 x y z a b c d hinj]; exact hzad · rw [fano_free_local_forbidden_map_245 x y z a b c d hinj]; exact hzbc
Finset.card_le_two- A set with at most two elements has cardinality at most 2.
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.map_eq_image- Mapping a finite set under an embedding is equal to taking the image under the underlying function.
Finset.image- The image of a finite set under a function.
fano_free_local_forbidden_card_three- If a three-element set has cardinality 3, then its elements are pairwise distinct.
fano_free_local_forbidden_injective- The map from Fin 7 to V sending 0 through 6 to x, y, z, a, b, c, d is injective when all 21 pairs of elements are distinct.
fano_plane- The standard Fano plane on Fin 7, defined as the set of seven 3-element blocks.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
fano_free_local_forbidden_map_012- The image of {0, 1, 2} under the 7-tuple embedding is {x, y, z}.
fano_free_local_forbidden_map_034- The image of {0, 3, 4} under the 7-tuple embedding is {x, a, b}.
fano_free_local_forbidden_map_056- The image of {0, 5, 6} under the 7-tuple embedding is {x, c, d}.
fano_free_local_forbidden_map_135- The image of {1, 3, 5} under the 7-tuple embedding is {y, a, c}.
fano_free_local_forbidden_map_146- The image of {1, 4, 6} under the 7-tuple embedding is {y, b, d}.
fano_free_local_forbidden_map_236- The image of {2, 3, 6} under the 7-tuple embedding is {z, a, d}.
fano_free_local_forbidden_map_245- The image of {2, 4, 5} under the 7-tuple embedding is {z, b, c}.
- In Lean, proving that seven vertices induce a Fano plane requires explicitly deriving all 21 pairwise inequalities from hyperedge cardinalities to establish injectivity of the vertex map, followed by verifying each of the seven lines individually.
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 fano_free_local_forbidden_card_three {V : Type*} [DecidableEq V] {p q r : V} (h : ({p,q,r} : Finset V).card = 3) : p ≠ q ∧ p ≠ r ∧ q ≠ r := by refine ⟨?_, ?_, ?_⟩ · intro heq have he : ({p,q,r} : Finset V) = {p,r} := by rw [heq]; simp have h1 : ({p,r} : Finset V).card = 3 := he ▸ h have h2 : ({p,r} : Finset V).card ≤ 2 := Finset.card_le_two omega · intro heq have he : ({p,q,r} : Finset V) = {q,r} := by rw [heq]; simp have h1 : ({q,r} : Finset V).card = 3 := he ▸ h have h2 : ({q,r} : Finset V).card ≤ 2 := Finset.card_le_two omega · intro heq have he : ({p,q,r} : Finset V) = {p,q} := by rw [heq]; simp have h1 : ({p,q} : Finset V).card = 3 := he ▸ h have h2 : ({p,q} : Finset V).card ≤ 2 := Finset.card_le_two omegaprivate lemma fano_free_local_forbidden_injective {V : Type*} [DecidableEq V] (x y z a b c d : V) (hxy : x ≠ y) (hxz : x ≠ z) (hyz : y ≠ z) (hxa : x ≠ a) (hxb : x ≠ b) (hab : a ≠ b) (hxc : x ≠ c) (hxd : x ≠ d) (hcd : c ≠ d) (hya : y ≠ a) (hyc : y ≠ c) (hac : a ≠ c) (hyb : y ≠ b) (hyd : y ≠ d) (hbd : b ≠ d) (hza : z ≠ a) (hzd : z ≠ d) (had : a ≠ d) (hzb : z ≠ b) (hzc : z ≠ c) (hbc : b ≠ c) : Function.Injective (![x, y, z, a, b, c, d] : Fin 7 → V) := by intro i j hij fin_cases i <;> fin_cases j <;> simp_all [Fin.ext_iff]private lemma fano_free_local_forbidden_map_012 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,1,2} : Finset (Fin 7)) = ({x,y,z} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_034 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,3,4} : Finset (Fin 7)) = ({x,a,b} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_056 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,5,6} : Finset (Fin 7)) = ({x,c,d} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_135 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({1,3,5} : Finset (Fin 7)) = ({y,a,c} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_146 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({1,4,6} : Finset (Fin 7)) = ({y,b,d} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_236 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({2,3,6} : Finset (Fin 7)) = ({z,a,d} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_245 {V : Type*} [DecidableEq V] (x y z a b c d : V) (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) : Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({2,4,5} : Finset (Fin 7)) = ({z,b,c} : Finset V) := by rw [Finset.map_eq_image]; simp [Finset.image]/-- Local forbidden constraint for Fano-free 3-graphs: no edge {x,y,z} can have six companion edges forming a Fano plane. -/theorem fano_free_local_forbidden {V : Type*} [DecidableEq V] (H : Finset (Finset V)) (hunif : is_three_uniform H) (hfree : is_fano_free H) (x y z a b c d : V) (hxyz : {x, y, z} ∈ H) : ¬ ({x, a, b} ∈ H ∧ {x, c, d} ∈ H ∧ {y, a, c} ∈ H ∧ {y, b, d} ∈ H ∧ {z, a, d} ∈ H ∧ {z, b, c} ∈ H) := by rintro ⟨hxab, hxcd, hyac, hybd, hzad, hzbc⟩ obtain ⟨hxy, hxz, hyz⟩ := fano_free_local_forbidden_card_three (hunif {x,y,z} hxyz) obtain ⟨hxa, hxb, hab⟩ := fano_free_local_forbidden_card_three (hunif {x,a,b} hxab) obtain ⟨hxc, hxd, hcd⟩ := fano_free_local_forbidden_card_three (hunif {x,c,d} hxcd) obtain ⟨hya, hyc, hac⟩ := fano_free_local_forbidden_card_three (hunif {y,a,c} hyac) obtain ⟨hyb, hyd, hbd⟩ := fano_free_local_forbidden_card_three (hunif {y,b,d} hybd) obtain ⟨hza, hzd, had⟩ := fano_free_local_forbidden_card_three (hunif {z,a,d} hzad) obtain ⟨hzb, hzc, hbc⟩ := fano_free_local_forbidden_card_three (hunif {z,b,c} hzbc) apply hfree have hinj : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V) := fano_free_local_forbidden_injective x y z a b c d hxy hxz hyz hxa hxb hab hxc hxd hcd hya hyc hac hyb hyd hbd hza hzd had hzb hzc hbc refine ⟨⟨![x,y,z,a,b,c,d], hinj⟩, ?_⟩ intro e he simp only [fano_plane, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl | rfl | rfl | rfl | rfl · rw [fano_free_local_forbidden_map_012 x y z a b c d hinj]; exact hxyz · rw [fano_free_local_forbidden_map_034 x y z a b c d hinj]; exact hxab · rw [fano_free_local_forbidden_map_056 x y z a b c d hinj]; exact hxcd · rw [fano_free_local_forbidden_map_135 x y z a b c d hinj]; exact hyac · rw [fano_free_local_forbidden_map_146 x y z a b c d hinj]; exact hybd · rw [fano_free_local_forbidden_map_236 x y z a b c d hinj]; exact hzad · rw [fano_free_local_forbidden_map_245 x y z a b c d hinj]; exact hzbc