AFTD Auto-Formalizing Theoretical Domains

token_graph

def

The k-token graph F_k(G) of a simple graph G has as vertices the k-subsets of V(G), with two k-subsets adjacent whenever their symmetric difference consists of two adjacent vertices in G.

Statement

def token_graph {V : Type*} [DecidableEq V] (G : SimpleGraph V) (k : ℕ) :
    SimpleGraph { s : Finset V // s.card = k }
Defined in
arXiv:2610.28936 Definition 2.5
Verified
25 Oct 2026
Axioms
none listed
Used by 14

Read back from the Lean

Given a type V with decidable equality, a simple graph G on V, and a natural number k, token_graph G k is the SimpleGraph whose vertices are the k-element finite subsets of V (the subtype { s : Finset V // s.card = k }), with two such subsets x and y being adjacent if and only if there exist vertices u, v : V such that u and v are adjacent in G and the symmetric difference symmDiff x.val y.val equals {u, v}.

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 k-token graph of a simple graph G. -/
def token_graph {V : Type*} [DecidableEq V] (G : SimpleGraph V) (k : ℕ) :
    SimpleGraph { s : Finset V // s.card = k } := {
  Adj := fun x y => ∃ u v : V, G.Adj u v ∧ symmDiff x.val y.val = {u, v}
  symm := ⟨by
    rintro ⟨x, hx⟩ ⟨y, hy⟩ ⟨u, v, hadj, hdiff⟩
    refine ⟨u, v, hadj, ?_⟩
    rw [symmDiff_comm, hdiff]⟩
  loopless := ⟨by
    rintro ⟨x, hx⟩ ⟨u, v, hadj, hdiff⟩
    have hne : u ≠ v := G.ne_of_adj hadj
    have hcard : ({u, v} : Finset V).card = 2 := Finset.card_pair hne
    have h0 : (symmDiff x x).card = 0 := by simp
    rw [hdiff] at h0
    omega⟩
}
See it in the graphDiscuss this resultChallenge it