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))