zycle_hom_implies_closed_walk
If f : ZMod ℓ × Fin 2 → α is a hypergraph homomorphism is_hypergraph_hom from the zycle Z_ℓ to a 3-uniform hypergraph G : Finset (Finset α), then there exists a closed walk W : ZMod ℓ → Finset α of length ℓ in the pair digraph of G satisfying pair_digraph_adj G (W i) (W (i + 1)) for all i in ZMod ℓ.
Statement
theorem zycle_hom_implies_closed_walk {α : Type*} [DecidableEq α] (ℓ : ℕ) [NeZero ℓ] (G : Finset (Finset α)) (hG : is_three_uniform G) (f : ZMod ℓ × Fin 2 → α) (hf : is_hypergraph_hom (zycle ℓ) G f) : ∃ W : ZMod ℓ → Finset α, ∀ i : ZMod ℓ, pair_digraph_adj G (W i) (W (i + 1))
- Formalizes
- arXiv:2611.16654 Lemma 2.3
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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),…
- 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 →…
- 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…
- 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.
- Used by 1
- zycle_not_div_three_no_hom_tripartite_turanLet ℓ ≥ 2 be an integer with 3 ∤ ℓ. For any family of pairwise disjoint finite sets V : ZMod 3 → Finset α, there is no function f : ZMod ℓ…
Read back from the Lean
Let α be a type with decidable equality, and let ℓ be a non-zero natural number. Let G be a finite collection of finite subsets of α such that every set in G has cardinality 3 (i.e., G is a 3-uniform hypergraph). Let f be a function from (ZMod ℓ × Fin 2) to α such that f is a hypergraph homomorphism from zycle ℓ to G (meaning that for every edge e of zycle ℓ, the image f(e) is in G).
Then there exists a sequence of 2-element subsets W : ZMod ℓ → Finset α such that for every i ∈ ZMod ℓ, W(i) is adjacent to W(i + 1) in the pair digraph of G; that is:
1. |W(i)| = 2,
2. |W(i + 1)| = 2, and
3. for every vertex v ∈ W(i + 1), the set W(i) ∪ {v} is in G.
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
To show that a homomorphism f from the zycle Z_ℓ to a 3-uniform hypergraph G induces a closed walk in the pair digraph D(G), the walk is explicitly defined by setting W(i) = {f(i, 0), f(i, 1)} for each i in ZMod ℓ. Each W(i) has cardinality 2 because its elements are part of a 3-element hyperedge image in G, forcing f(i, 0) ≠ f(i, 1). Finally, for any vertex v in W(i+1), the set W(i) ∪ {v} is the image under f of one of the two hyperedges of Z_ℓ at step i, hence belongs to G by the homomorphism property, completing the adjacency requirement in D(G).
If a finset {a, b, c} has cardinality 3, then a ≠ b.
Suppose for contradiction that a = b. Then the three-element finset {a, b, c} collapses to {a, c}, which by Finset.card_le_two has cardinality at most 2. This directly contradicts the assumption that its cardinality is 3.
uses
Finset.card_le_twoprivate lemma zycle_hom_implies_closed_walk_card_three_ne {α : Type*} [DecidableEq α] {a b c : α} (h : ({a,b,c} : Finset α).card = 3) : a ≠ b := by intro hab have key : ({a,b,c} : Finset α) = {a,c} := by ext x; simp [hab] rw [key] at h have := Finset.card_le_two (α := α) (a := a) (b := c) omega
For each i ∈ ZMod ℓ, the image under f of {(i, 0), (i, 1), (i+1, 0)} is {f (i, 0), f (i, 1), f (i+1, 0)}, and similarly the image of {(i, 0), (i, 1), (i+1, 1)} is {f (i, 0), f (i, 1), f (i+1, 1)}.
For each index i, set extensionality reduces equality of finsets to equivalence of membership. Using Finset.mem_image, Finset.mem_insert, and Finset.mem_singleton, an element x belongs to the image Finset.image f {(i,0), (i,1), (i+1,0)} if and only if x = f(i,0), x = f(i,1), or x = f(i+1,0). The two directions of the equivalence are verified by case analysis on the disjunctions using Or.inl and Or.inr. The identical argument applies to the second triple.
uses
Finset.mem_image,Finset.mem_insert,Finset.mem_singleton,Or.inl,Or.inr/-- A homomorphism from Z_ℓ to a 3-uniform hypergraph G implies a closed walk of length ℓ in D(G). -/ theorem zycle_hom_implies_closed_walk {α : Type*} [DecidableEq α] (ℓ : ℕ) [NeZero ℓ] (G : Finset (Finset α)) (hG : is_three_uniform G) (f : ZMod ℓ × Fin 2 → α) (hf : is_hypergraph_hom (zycle ℓ) G f) : ∃ W : ZMod ℓ → Finset α, ∀ i : ZMod ℓ, pair_digraph_adj G (W i) (W (i + 1)) := by classical have himg1 : ∀ i : ZMod ℓ, Finset.image f ({(i,0),(i,1),(i+1,0)} : Finset (ZMod ℓ × Fin 2)) = ({f (i,0), f (i,1), f (i+1,0)} : Finset α) := by intro i ext x; simp only [Finset.mem_image, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨a, h1 | h1 | h1, hx⟩ · subst h1; exact Or.inl hx.symm · subst h1; exact Or.inr (Or.inl hx.symm) · subst h1; exact Or.inr (Or.inr hx.symm) · rintro (rfl | rfl | rfl) · exact ⟨(i,0), Or.inl rfl, rfl⟩ · exact ⟨(i,1), Or.inr (Or.inl rfl), rfl⟩ · exact ⟨(i+1,0), Or.inr (Or.inr rfl), rfl⟩ have himg2 : ∀ i : ZMod ℓ, Finset.image f ({(i,0),(i,1),(i+1,1)} : Finset (ZMod ℓ × Fin 2)) = ({f (i,0), f (i,1), f (i+1,1)} : Finset α) := by intro i ext x; simp only [Finset.mem_image, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨a, h1 | h1 | h1, hx⟩ · subst h1; exact Or.inl hx.symm · subst h1; exact Or.inr (Or.inl hx.symm) · subst h1; exact Or.inr (Or.inr hx.symm) · rintro (rfl | rfl | rfl) · exact ⟨(i,0), Or.inl rfl, rfl⟩ · exact ⟨(i,1), Or.inr (Or.inl rfl), rfl⟩ · exact ⟨(i+1,1), Or.inr (Or.inr rfl), rfl⟩
For every i ∈ ZMod ℓ, the triples {(i, 0), (i, 1), (i+1, 0)} and {(i, 0), (i, 1), (i+1, 1)} are hyperedges of zycle ℓ; their images under f belong to G and have cardinality 3.
By definition of zycle ℓ as an indexed union (biUnion) over all i in the universal finset ZMod ℓ, both triples are members of zycle ℓ, as shown using Finset.mem_biUnion.mpr and Finset.mem_univ. Since f is a hypergraph homomorphism (hf), the image of any hyperedge of the zycle belongs to G. Furthermore, because G is 3-uniform (hG), every hyperedge in G has cardinality 3, so both image sets have cardinality 3.
uses
Finset.mem_biUnion.mpr,Finset.mem_univhave hmem1 : ∀ i : ZMod ℓ, ({(i,0),(i,1),(i+1,0)} : Finset (ZMod ℓ × Fin 2)) ∈ zycle ℓ := by intro i simp only [zycle] apply Finset.mem_biUnion.mpr exact ⟨i, Finset.mem_univ i, by simp⟩ have hmem2 : ∀ i : ZMod ℓ, ({(i,0),(i,1),(i+1,1)} : Finset (ZMod ℓ × Fin 2)) ∈ zycle ℓ := by intro i simp only [zycle] apply Finset.mem_biUnion.mpr exact ⟨i, Finset.mem_univ i, by simp⟩ have hG1 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,0)} : Finset α) ∈ G := by intro i; rw [← himg1 i]; exact hf _ (hmem1 i) have hG2 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,1)} : Finset α) ∈ G := by intro i; rw [← himg2 i]; exact hf _ (hmem2 i) have hcard1 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,0)} : Finset α).card = 3 := fun i => hG _ (hG1 i) have hcard2 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,1)} : Finset α).card = 3 := fun i => hG _ (hG2 i)
Defining the candidate walk W(i) = {f(i, 0), f(i, 1)}, each vertex W(i) and W(i+1) has cardinality 2.
We instantiate the existential closed walk with W(i) = {f(i, 0), f(i, 1)}. Unfolding the definition of pair_digraph_adj G (W i) (W (i+1)) requires showing |W(i)| = 2, |W(i+1)| = 2, and the adjacency condition. Because the image triple {f(i, 0), f(i, 1), f(i+1, 0)} has cardinality 3, the helper lemma zycle_hom_implies_closed_walk_card_three_ne ensures that f(i, 0) ≠ f(i, 1). Thus Finset.card_pair proves |W(i)| = 2. The exact same argument at index i+1 proves |W(i+1)| = 2.
uses
Finset.card_pair,zycle_hom_implies_closed_walk_card_three_nerefine ⟨fun i => ({f (i,0), f (i,1)} : Finset α), ?_⟩ intro i rw [pair_digraph_adj] refine ⟨?_, ?_, ?_⟩ · apply Finset.card_pair exact zycle_hom_implies_closed_walk_card_three_ne (hcard1 i) · apply Finset.card_pair exact zycle_hom_implies_closed_walk_card_three_ne (hcard1 (i+1))
For every v ∈ W(i+1), the set W(i) ∪ {v} is a hyperedge in G, establishing pair_digraph_adj G (W i) (W (i+1)).
An element v ∈ W(i+1) = {f(i+1, 0), f(i+1, 1)} is either f(i+1, 0) or f(i+1, 1). In the first case, W(i) ∪ {v} equals {f(i, 0), f(i, 1), f(i+1, 0)}, which was shown to belong to G. In the second case, W(i) ∪ {v} equals {f(i, 0), f(i, 1), f(i+1, 1)}, which also belongs to G. This verifies the third and final condition of pair_digraph_adj.
uses
Finset.mem_insert,Finset.mem_singleton· intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with rfl | rfl · rw [show (({f (i,0), f (i,1)} : Finset α) ∪ {f (i+1,0)}) = {f (i,0), f (i,1), f (i+1,0)} from by ext x; simp] exact hG1 i · rw [show (({f (i,0), f (i,1)} : Finset α) ∪ {f (i+1,1)}) = {f (i,0), f (i,1), f (i+1,1)} from by ext x; simp] exact hG2 i
Finset.card_le_two- For any elements a and b, the finset {a, b} has cardinality at most 2.
Finset.mem_image- An element b is in the image of a finset s under f if and only if there exists a ∈ s such that f a = b.
Finset.mem_insert- An element a belongs to insert b s if and only if a = b or a ∈ s.
Finset.mem_singleton- An element b belongs to the singleton {a} if and only if b = a.
Or.inl- From a proof of proposition a, derives the disjunction a ∨ b.
Or.inr- From a proof of proposition b, derives the disjunction a ∨ b.
Finset.mem_biUnion.mpr- If there exists an element a ∈ s such that b ∈ t a, then b belongs to the indexed union Finset.biUnion s t.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
Finset.card_pair- If a ≠ b, then the finset {a, b} has cardinality 2.
zycle_hom_implies_closed_walk_card_three_ne- If the finset {a, b, c} has cardinality 3, then a ≠ b.
- A significant portion of the formal proof (lines 15–40) is devoted to verifying by element-wise extensionality that the image of a three-element finset under f is syntactically equal to the finset of images; on paper, this identity holds immediately by definition.
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 zycle_hom_implies_closed_walk_card_three_ne {α : Type*} [DecidableEq α] {a b c : α} (h : ({a,b,c} : Finset α).card = 3) : a ≠ b := by intro hab have key : ({a,b,c} : Finset α) = {a,c} := by ext x; simp [hab] rw [key] at h have := Finset.card_le_two (α := α) (a := a) (b := c) omega/-- A homomorphism from Z_ℓ to a 3-uniform hypergraph G implies a closed walk of length ℓ in D(G). -/theorem zycle_hom_implies_closed_walk {α : Type*} [DecidableEq α] (ℓ : ℕ) [NeZero ℓ] (G : Finset (Finset α)) (hG : is_three_uniform G) (f : ZMod ℓ × Fin 2 → α) (hf : is_hypergraph_hom (zycle ℓ) G f) : ∃ W : ZMod ℓ → Finset α, ∀ i : ZMod ℓ, pair_digraph_adj G (W i) (W (i + 1)) := by classical have himg1 : ∀ i : ZMod ℓ, Finset.image f ({(i,0),(i,1),(i+1,0)} : Finset (ZMod ℓ × Fin 2)) = ({f (i,0), f (i,1), f (i+1,0)} : Finset α) := by intro i ext x; simp only [Finset.mem_image, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨a, h1 | h1 | h1, hx⟩ · subst h1; exact Or.inl hx.symm · subst h1; exact Or.inr (Or.inl hx.symm) · subst h1; exact Or.inr (Or.inr hx.symm) · rintro (rfl | rfl | rfl) · exact ⟨(i,0), Or.inl rfl, rfl⟩ · exact ⟨(i,1), Or.inr (Or.inl rfl), rfl⟩ · exact ⟨(i+1,0), Or.inr (Or.inr rfl), rfl⟩ have himg2 : ∀ i : ZMod ℓ, Finset.image f ({(i,0),(i,1),(i+1,1)} : Finset (ZMod ℓ × Fin 2)) = ({f (i,0), f (i,1), f (i+1,1)} : Finset α) := by intro i ext x; simp only [Finset.mem_image, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨a, h1 | h1 | h1, hx⟩ · subst h1; exact Or.inl hx.symm · subst h1; exact Or.inr (Or.inl hx.symm) · subst h1; exact Or.inr (Or.inr hx.symm) · rintro (rfl | rfl | rfl) · exact ⟨(i,0), Or.inl rfl, rfl⟩ · exact ⟨(i,1), Or.inr (Or.inl rfl), rfl⟩ · exact ⟨(i+1,1), Or.inr (Or.inr rfl), rfl⟩ have hmem1 : ∀ i : ZMod ℓ, ({(i,0),(i,1),(i+1,0)} : Finset (ZMod ℓ × Fin 2)) ∈ zycle ℓ := by intro i simp only [zycle] apply Finset.mem_biUnion.mpr exact ⟨i, Finset.mem_univ i, by simp⟩ have hmem2 : ∀ i : ZMod ℓ, ({(i,0),(i,1),(i+1,1)} : Finset (ZMod ℓ × Fin 2)) ∈ zycle ℓ := by intro i simp only [zycle] apply Finset.mem_biUnion.mpr exact ⟨i, Finset.mem_univ i, by simp⟩ have hG1 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,0)} : Finset α) ∈ G := by intro i; rw [← himg1 i]; exact hf _ (hmem1 i) have hG2 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,1)} : Finset α) ∈ G := by intro i; rw [← himg2 i]; exact hf _ (hmem2 i) have hcard1 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,0)} : Finset α).card = 3 := fun i => hG _ (hG1 i) have hcard2 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,1)} : Finset α).card = 3 := fun i => hG _ (hG2 i) refine ⟨fun i => ({f (i,0), f (i,1)} : Finset α), ?_⟩ intro i rw [pair_digraph_adj] refine ⟨?_, ?_, ?_⟩ · apply Finset.card_pair exact zycle_hom_implies_closed_walk_card_three_ne (hcard1 i) · apply Finset.card_pair exact zycle_hom_implies_closed_walk_card_three_ne (hcard1 (i+1)) · intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with rfl | rfl · rw [show (({f (i,0), f (i,1)} : Finset α) ∪ {f (i+1,0)}) = {f (i,0), f (i,1), f (i+1,0)} from by ext x; simp] exact hG1 i · rw [show (({f (i,0), f (i,1)} : Finset α) ∪ {f (i+1,1)}) = {f (i,0), f (i,1), f (i+1,1)} from by ext x; simp] exact hG2 i