cartesian_product_complete_graphs
The Cartesian product of t complete graphs with sizes given by a : Fin t → ℕ, defined as a simple graph on vertex type (i : Fin t) → Fin (a i), where two vertices are adjacent if and only if they differ in exactly one coordinate.
Statement
def cartesian_product_complete_graphs {t : ℕ} (a : Fin t → ℕ) :
SimpleGraph ((i : Fin t) → Fin (a i))- Defined in
- arXiv:2611.03956, Definition 2.6
- Verified
- 04 Nov 2026
- Axioms
- none listed
Read back from the Lean
Given a natural number $t$ (implicit) and a sequence of natural numbers $a : \text{Fin } t \to \mathbb{N}$, cartesian_product_complete_graphs a is the simple graph with vertex type $\prod_{i : \text{Fin } t} \text{Fin}(a(i))$ (functions $u$ mapping each $i : \text{Fin } t$ to an element of $\text{Fin}(a(i))$), where two vertices $u$ and $v$ are adjacent if and only if there exists a coordinate $j : \text{Fin } t$ such that $u(j) \neq v(j)$ and for all $i : \text{Fin } t$ with $i \neq j$, $u(i) = v(i)$ (i.e., $u$ and $v$ differ at exactly one coordinate).
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
/-- Cartesian product of t complete graphs with vertex set (i : Fin t) → Fin (a i). -/ def cartesian_product_complete_graphs {t : ℕ} (a : Fin t → ℕ) : SimpleGraph ((i : Fin t) → Fin (a i)) := by refine SimpleGraph.mk (fun u v => ∃ j : Fin t, u j ≠ v j ∧ ∀ i : Fin t, i ≠ j → u i = v i) ?_ ?_ · exact Std.Symm.mk (by intro u v ⟨j, hj, hrest⟩ exact ⟨j, hj.symm, fun i hi => (hrest i hi).symm⟩) · exact Std.Irrefl.mk (by intro u ⟨j, hj, _⟩ exact hj rfl)