zycle_not_div_three_no_hom_tripartite_turan
Let ℓ ≥ 2 be an integer with 3 ∤ ℓ. For any family of pairwise disjoint finite sets V : ZMod 3 → Finset α, there is no function f : ZMod ℓ × Fin 2 → α that is a hypergraph homomorphism is_hypergraph_hom from the zycle Z_ℓ to the tripartite Turán construction tripartite_turan_hypergraph V.
Statement
theorem zycle_not_div_three_no_hom_tripartite_turan {α : Type*} [DecidableEq α] (ℓ : ℕ) [NeZero ℓ] (hℓ_ge : 2 ≤ ℓ) (hℓ_not_dvd : ¬ 3 ∣ ℓ) (V : ZMod 3 → Finset α) (hdisj : ∀ i j : ZMod 3, i ≠ j → Disjoint (V i) (V j)) : ¬ ∃ f : ZMod ℓ × Fin 2 → α, is_hypergraph_hom (zycle ℓ) (tripartite_turan_hypergraph V) f
- Formalizes
- arXiv:2611.16654 Lemma 3.3
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- zycleFor any positive integer ℓ, the 3-uniform zycle Z_ℓ has vertex set ZMod ℓ × Fin 2 and edge set consisting of the triples {(i,0), (i,1),…
- tripartite_turan_hypergraphGiven a type α with decidable equality and a family of finite sets V : ZMod 3 → Finset α, tripartite_turan_hypergraph V is the finite set…
- is_hypergraph_homFor types V and W with decidable equality on W, finite hyperedge sets F : Finset (Finset V) and G : Finset (Finset W), and a map f : V →…
- tripartite_turan_hypergraph_three_uniformFor any family of finite sets V : ZMod 3 → Finset α, the tripartite Turán hypergraph tripartite_turan_hypergraph V is 3-uniform…
- zycle_hom_implies_closed_walkIf f : ZMod ℓ × Fin 2 → α is a hypergraph homomorphism is_hypergraph_hom from the zycle Z_ℓ to a 3-uniform hypergraph G : Finset (Finset…
- tripartite_turan_pair_digraph_no_closed_walkFor any family of pairwise disjoint finite sets V : ZMod 3 → Finset α and any integer ℓ with 3 ∤ ℓ, there is no closed walk W : ZMod ℓ →…
- pair_digraph_adjTwo pairs P and Q of vertices form a directed arc P → Q in the pair digraph D(G) of a 3-uniform hypergraph G if both have cardinality 2…
Read back from the Lean
For any type α with decidable equality, any positive integer ℓ such that 2 ≤ ℓ and 3 does not divide ℓ, and any family of three pairwise disjoint finite subsets V 0, V 1, V 2 of α, there does not exist a function f : (ZMod ℓ × Fin 2) → α that is a hypergraph homomorphism from the 3-uniform cycle hypergraph zycle ℓ to the tripartite Turán 3-hypergraph tripartite_turan_hypergraph V.
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 proof proceeds by contradiction. Assuming there is a hypergraph homomorphism from the zycle Z_ℓ to the tripartite Turán hypergraph, the 3-uniformity of the Turán hypergraph ensures that this homomorphism induces a closed directed walk of length ℓ in the hypergraph's pair digraph. However, because the three vertex classes are pairwise disjoint and 3 does not divide ℓ, the pair digraph contains no closed walk of length ℓ, producing a contradiction.
Assume for contradiction that there exists a hypergraph homomorphism f from the zycle Z_ℓ to the tripartite Turán hypergraph T(V).
We assume the negation of the goal, obtaining a candidate homomorphism f : ZMod ℓ × Fin 2 → α and the hypothesis hf that every hyperedge of Z_ℓ maps to a hyperedge in the tripartite Turán construction.
rintro ⟨f, hf⟩
There exists a closed directed walk of length ℓ in the pair digraph of the tripartite Turán hypergraph.
By tripartite_turan_hypergraph_three_uniform, the tripartite Turán hypergraph is 3-uniform. Applying zycle_hom_implies_closed_walk to this 3-uniform hypergraph and the homomorphism f produces a sequence of pairs forming a closed walk W of length ℓ in its pair digraph.
uses
zycle_hom_implies_closed_walk,tripartite_turan_hypergraph_three_uniformhave hwalk := zycle_hom_implies_closed_walk ℓ (tripartite_turan_hypergraph V) (tripartite_turan_hypergraph_three_uniform V) f hfThe existence of this closed walk leads to a contradiction, concluding that no such homomorphism exists.
By tripartite_turan_pair_digraph_no_closed_walk, because the vertex parts V i are pairwise disjoint and 3 does not divide ℓ, the pair digraph cannot have any closed walk of length ℓ. This directly contradicts the closed walk W obtained in the previous step.
uses
tripartite_turan_pair_digraph_no_closed_walkexact tripartite_turan_pair_digraph_no_closed_walk V hdisj ℓ hℓ_not_dvd hwalk
zycle_hom_implies_closed_walk- Given a 3-uniform hypergraph G, any hypergraph homomorphism from the zycle Z_ℓ to G induces a closed directed walk of length ℓ in the pair digraph of G.
tripartite_turan_hypergraph_three_uniform- The tripartite Turán hypergraph built from three sets is 3-uniform (all of its hyperedges contain exactly 3 vertices).
tripartite_turan_pair_digraph_no_closed_walk- If the three vertex sets V i are pairwise disjoint and 3 does not divide ℓ, then the pair digraph of the tripartite Turán hypergraph admits no closed directed walk of length ℓ.
- The hypothesis `hℓ_ge : 2 ≤ ℓ` is included in the theorem signature, but it is not used in the proof; nonzeroness (`NeZero ℓ`) and non-divisibility (`¬ 3 ∣ ℓ`) suffice for the referenced lemmas.
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.
/-- There is no hypergraph homomorphism from Z_ℓ to T[V₁, V₂, V₃] when 3 does not divide ℓ. -/theorem zycle_not_div_three_no_hom_tripartite_turan {α : Type*} [DecidableEq α] (ℓ : ℕ) [NeZero ℓ] (hℓ_ge : 2 ≤ ℓ) (hℓ_not_dvd : ¬ 3 ∣ ℓ) (V : ZMod 3 → Finset α) (hdisj : ∀ i j : ZMod 3, i ≠ j → Disjoint (V i) (V j)) : ¬ ∃ f : ZMod ℓ × Fin 2 → α, is_hypergraph_hom (zycle ℓ) (tripartite_turan_hypergraph V) f := by rintro ⟨f, hf⟩ have hwalk := zycle_hom_implies_closed_walk ℓ (tripartite_turan_hypergraph V) (tripartite_turan_hypergraph_three_uniform V) f hf exact tripartite_turan_pair_digraph_no_closed_walk V hdisj ℓ hℓ_not_dvd hwalk