supertoken_graph
The supertoken graph F^s_{k x 1}(G) of a simple graph G has as vertices the k-tuples of vertices of G with at most s occurrences of any vertex, where two configurations are adjacent if they differ at exactly one token moved along an edge of G.
Statement
def supertoken_graph {V : Type*} [DecidableEq V] (G : SimpleGraph V) (k s : ℕ) : SimpleGraph { x : Fin k → V // ∀ v : V, (Finset.univ.filter (fun i => x i = v)).card ≤ s }
- Defined in
- arXiv:2611.06275, Section 1
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 2
- supertoken_graph_regular_of_degree_le_sLet G be a finite simple d-regular graph on vertex type V, and let s and k be natural numbers such that k ≤ s. Then the supertoken graph…
- supertoken_graph_bipartiteLet G be a finite bipartite simple graph on vertex type V with decidable equality (satisfying G.IsBipartite). Let s ≥ 1 and 1 ≤ k ≤ s *…
Read back from the Lean
Given a type V with decidable equality, a simple graph G on V, and natural numbers k and s, supertoken_graph G k s is the simple graph whose vertex type is the subtype of functions x : Fin k → V satisfying that for all v : V, the number of indices i : Fin k with x i = v is at most s, and whose adjacency relation is defined by: x and y are adjacent if and only if there exists an index i : Fin k such that x i and y i are adjacent in G, and for all j : Fin k with j ≠ i, x j = y 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 supertoken graph F^s_{k x 1}(G) with k distinguishable tokens and maximum capacity s per vertex. -/ def supertoken_graph {V : Type*} [DecidableEq V] (G : SimpleGraph V) (k s : ℕ) : SimpleGraph { x : Fin k → V // ∀ v : V, (Finset.univ.filter (fun i => x i = v)).card ≤ s } := { Adj := fun x y => ∃ i : Fin k, G.Adj (x.1 i) (y.1 i) ∧ ∀ j : Fin k, j ≠ i → x.1 j = y.1 j symm := ⟨by rintro ⟨x, hx⟩ ⟨y, hy⟩ ⟨i, hadj, heq⟩ exact ⟨i, G.adj_symm hadj, fun j hj => (heq j hj).symm⟩⟩ loopless := ⟨by rintro ⟨x, hx⟩ ⟨i, hadj, -⟩ exact G.loopless.irrefl (x i) hadj⟩ }