AFTD Auto-Formalizing Theoretical Domains

cartesian_power_graph

def

The n-fold Cartesian power of a graph G, with vertices given by functions from Fin n to V, where two vertices are adjacent if and only if they differ in exactly one coordinate and are adjacent in G at that coordinate.

Statement

def cartesian_power_graph {V : Type*} (G : SimpleGraph V) (n : ℕ) : SimpleGraph (Fin n → V)
Defined in
arXiv:2610.36620, Section 3.1
Verified
29 Oct 2026
Axioms
none listed

Read back from the Lean

Given a type V, a simple graph G on V, and a natural number n, cartesian_power_graph G n is defined as the simple graph on vertices Fin n → V constructed via SimpleGraph.fromRel from the binary relation: there exists an index i : Fin n such that f i and g i are adjacent in G, and for all indices j : Fin n with j ≠ i, f j = g j.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The n-fold Cartesian power of a simple graph. -/
def cartesian_power_graph {V : Type*} (G : SimpleGraph V) (n : ℕ) : SimpleGraph (Fin n → V) := SimpleGraph.fromRel (fun f g => ∃ i : Fin n, G.Adj (f i) (g i) ∧ (∀ j : Fin n, j ≠ i → f j = g j))
See it in the graphDiscuss this resultChallenge it