AFTD Auto-Formalizing Theoretical Domains

zycle_not_div_three_no_hom_tripartite_turan

theoremverifiedformalization

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.

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

    line 7

      rintro ⟨f, hf⟩
  2. 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.

    lines 8–9

    uses zycle_hom_implies_closed_walk, tripartite_turan_hypergraph_three_uniform

      have hwalk := zycle_hom_implies_closed_walk ℓ (tripartite_turan_hypergraph V)
        (tripartite_turan_hypergraph_three_uniform V) f hf
  3. The 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.

    line 10

    uses tripartite_turan_pair_digraph_no_closed_walk

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

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

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