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
- two_token_domination_number_even_matching_leLet G be a finite simple graph on vertex type V whose complement graph Gᶜ is 1-regular. Then the domination number of the 2-token graph…
- three_token_k2n_assemble_layer_coverIf the explicit candidate family has the claimed cardinality and dominates every configuration in each of the three possible left-token…
- two_token_domination_number_ge_ceil_halfLet G be a finite simple graph on vertex type V with domination number at least 2. Then the domination number of the 2-token graph F_2(G)…
- three_token_k2n_domination_number_fourThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is 4.
- three_token_star_domination_number_fourThe domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 4)) is 3.
- two_token_domination_number_boundLet G be a finite simple graph on vertex type V with domination number at least 2. Then the domination number of the 2-token graph F_2(G)…
- three_token_k2n_assemble_three_layersIf the explicit candidate family has the claimed cardinality and dominates each of the layers with zero, one and two left-part tokens, the…
- three_token_star_domination_number_threeThe domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 3)) is 1.
- three_token_k2n_domination_number_four_geThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at least 4.
- two_token_dominating_set_card_ge_ceil_halfLet G be a finite simple graph on vertex type V with domination number at least 2. Then every dominating set D of the 2-token graph F_2(G)…
- two_token_kmnThe 2-token graph F_2(K_{m,n}) of the complete bipartite graph K_{m,n}.
- three_token_k2n_domination_number_four_leThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at most 4.
- three_token_star_domination_number_three_leThe domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 3)) is at most 1.
- two_token_domination_number_odd_p3_matching_leLet G be a finite simple graph on vertex type V whose complement graph Gᶜ has a unique vertex of degree 2 and all other vertices of degree…
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⟩ }