supertoken_graph_regular_of_degree_le_s
Let 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 G k s is regular of degree k * d.
Statement
open scoped Classical in theorem supertoken_graph_regular_of_degree_le_s {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (d : ℕ) (hreg : G.IsRegularOfDegree d) (s : ℕ) (k : ℕ) (hk : k ≤ s) : (supertoken_graph G k s).IsRegularOfDegree (k * d)
- Source
- arXiv:2611.06275 Theorem 2.4
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- supertoken_graphThe 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…
Read back from the Lean
For any finite type V with decidable equality, any simple graph G on V, any natural number d such that G is regular of degree d, and any natural numbers s and k satisfying k ≤ s, the supertoken graph supertoken_graph G k s is regular of degree k * d.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the supertoken graph is regular of degree k * d, the proof establishes a bijection between the neighbor set of any configuration x and the disjoint union of the neighbor sets of all its tokens, Σ_{i ∈ Fin k} G.neighborSet (x(i)). Injectivity holds because the looplessness of G uniquely identifies which token moved and where, while surjectivity follows directly from the definition of edges in the supertoken graph. Since G is d-regular, summing the d neighbors available to each of the k tokens gives degree k * d.
Any configuration of k tokens places at most s tokens at any vertex, provided k ≤ s.
The set of indices mapped to a vertex v is a subset of the domain Fin k of size k, so its cardinality is at most k by Finset.card_filter_le. Since k ≤ s, transitivity via supertoken_graph_regular_of_degree_le_s_card_filter_le_k yields that the number of tokens at v is at most s.
uses
Finset.card_filter_le,supertoken_graph_regular_of_degree_le_s_card_filter_le_klemma supertoken_graph_regular_of_degree_le_s_card_filter_le_k {V : Type*} [DecidableEq V] {k : ℕ} (x : Fin k → V) (v : V) : (Finset.univ.filter (fun i => x i = v)).card ≤ k := by have : (Finset.univ.filter (fun i => x i = v)).card ≤ (Finset.univ : Finset (Fin k)).card := Finset.card_filter_le _ _ simpa using this lemma supertoken_graph_regular_of_degree_le_s_card_filter_le_s {V : Type*} [DecidableEq V] {k s : ℕ} (hk : k ≤ s) (x : Fin k → V) (v : V) : (Finset.univ.filter (fun i => x i = v)).card ≤ s := (supertoken_graph_regular_of_degree_le_s_card_filter_le_k x v).trans hk
Construct a map sending each pair (i, u), where u is a neighbor of x(i) in G, to a valid neighbor x[i ↦ u] of x in the supertoken graph.
Updating the token configuration x at index i to u satisfies the vertex capacity constraint (≤ s tokens per vertex) by supertoken_graph_regular_of_degree_le_s_card_filter_le_s. The resulting configuration is adjacent to x in the supertoken graph because at position i the token moves to the neighbor u (via Function.update_self), while all other tokens j ≠ i remain stationary (via Function.update_of_ne).
uses
supertoken_graph_regular_of_degree_le_s_card_filter_le_s,Function.update_self,Function.update_of_nedef supertoken_graph_regular_of_degree_le_s_to_neighbor {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (k s : ℕ) (hk : k ≤ s) (x : { x : Fin k → V // ∀ v : V, (Finset.univ.filter (fun i => x i = v)).card ≤ s }) (p : Σ (i : Fin k), G.neighborSet (x.1 i)) : (supertoken_graph G k s).neighborSet x := ⟨⟨Function.update x.1 p.1 p.2.1, supertoken_graph_regular_of_degree_le_s_card_filter_le_s hk _⟩, by dsimp [supertoken_graph] refine ⟨p.1, ?_, ?_⟩ · dsimp rw [Function.update_self] exact p.2.2 · intro j hj dsimp rw [Function.update_of_ne hj]⟩
Assuming two pairs (i₁, u₁) and (i₂, u₂) map to the same neighbor, their updated configurations are equal as functions, and u₁ cannot equal x(i₁).
Applying congr_arg Subtype.val twice to the hypothesis shows that the updated configurations x[i₁ ↦ u₁] and x[i₂ ↦ u₂] are identical functions. Moreover, because u₁ is adjacent to x(i₁) in the simple graph G and G has no self-loops, u₁ ≠ x(i₁).
uses
congr_arg,Subtype.vallemma supertoken_graph_regular_of_degree_le_s_to_neighbor_inj {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (k s : ℕ) (hk : k ≤ s) (x : { x : Fin k → V // ∀ v : V, (Finset.univ.filter (fun i => x i = v)).card ≤ s }) : Function.Injective (supertoken_graph_regular_of_degree_le_s_to_neighbor G k s hk x) := by rintro ⟨i₁, u₁, hu₁⟩ ⟨i₂, u₂, hu₂⟩ h have hfn : Function.update x.1 i₁ u₁ = Function.update x.1 i₂ u₂ := by have h1 := congr_arg Subtype.val h exact congr_arg Subtype.val h1 have h_ne1 : u₁ ≠ x.1 i₁ := by intro heq have hadj : G.Adj (x.1 i₁) u₁ := hu₁ rw [heq] at hadj exact hadj.ne rfl
The indices of the moved tokens must coincide: i₁ = i₂.
Suppose for contradiction that i₁ ≠ i₂. Evaluating both sides of the function equality at i₁, the left side evaluates to u₁ by Function.update_self, whereas the right side evaluates to x(i₁) by Function.update_of_ne since i₁ ≠ i₂. This would imply u₁ = x(i₁), contradicting looplessness. Hence i₁ = i₂.
uses
Function.update_self,Function.update_of_nehave hi : i₁ = i₂ := by by_contra hne have h1 : Function.update x.1 i₁ u₁ i₁ = Function.update x.1 i₂ u₂ i₁ := by rw [hfn] simp only [Function.update_self] at h1 rw [Function.update_of_ne hne] at h1 exact h_ne1 h1 subst hi
The destination vertices must coincide (u₁ = u₂), completing the proof that the map is injective.
Knowing i₁ = i₂, evaluating both sides of the function equality at index i₁ yields u₁ = u₂ via Function.update_self. Therefore the two pairs are equal, establishing injectivity.
uses
Function.update_selfhave hu : u₁ = u₂ := by have h1 : Function.update x.1 i₁ u₁ i₁ = Function.update x.1 i₁ u₂ i₁ := by rw [hfn] simp only [Function.update_self] at h1 exact h1 subst hu rfl
The map to neighbors is surjective.
Given a neighbor y of x in the supertoken graph, by definition there is an index i such that y(i) is adjacent to x(i) in G and y(j) = x(j) for all j ≠ i. Taking the pair (i, y(i)), evaluating the updated configuration at j = i gives y(i) by Function.update_self, and at j ≠ i gives x(j) = y(j) by Function.update_of_ne. Thus (i, y(i)) maps precisely to y.
uses
supertoken_graph_regular_of_degree_le_s_to_neighbor,Function.update_self,Function.update_of_nelemma supertoken_graph_regular_of_degree_le_s_to_neighbor_surj {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (k s : ℕ) (hk : k ≤ s) (x : { x : Fin k → V // ∀ v : V, (Finset.univ.filter (fun i => x i = v)).card ≤ s }) : Function.Surjective (supertoken_graph_regular_of_degree_le_s_to_neighbor G k s hk x) := by rintro ⟨y, hy⟩ obtain ⟨i, hadj, heq⟩ := hy have hu : y.1 i ∈ G.neighborSet (x.1 i) := hadj refine ⟨⟨i, ⟨y.1 i, hu⟩⟩, ?_⟩ ext1 ext1 ext j dsimp [supertoken_graph_regular_of_degree_le_s_to_neighbor] by_cases hji : j = i · subst hji rw [Function.update_self] · rw [Function.update_of_ne hji] exact heq j hji
For every vertex x in the supertoken graph, its neighbor set has cardinality k * d.
Because the map is injective (supertoken_graph_regular_of_degree_le_s_to_neighbor_inj) and surjective (supertoken_graph_regular_of_degree_le_s_to_neighbor_surj), Equiv.ofBijective turns it into an equivalence between the neighbor set and the sigma type Σ (i : Fin k), G.neighborSet (x i). By Fintype.card_congr and Fintype.card_sigma, the neighbor set cardinality equals the sum over i ∈ Fin k of |G.neighborSet (x i)|. Using SimpleGraph.card_neighborSet_eq_degree and the d-regularity of G (hreg), each term is d. Summing d over the k tokens gives k * d.
uses
Equiv.ofBijective,supertoken_graph_regular_of_degree_le_s_to_neighbor,supertoken_graph_regular_of_degree_le_s_to_neighbor_inj,supertoken_graph_regular_of_degree_le_s_to_neighbor_surj,Fintype.card_congr,Fintype.card_sigma,SimpleGraph.card_neighborSet_eq_degreeopen scoped Classical in /-- The supertoken graph of a d-regular graph with k ≤ s tokens is regular of degree kd. -/ theorem supertoken_graph_regular_of_degree_le_s {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (d : ℕ) (hreg : G.IsRegularOfDegree d) (s : ℕ) (k : ℕ) (hk : k ≤ s) : (supertoken_graph G k s).IsRegularOfDegree (k * d) := by intro x have hcard : Fintype.card ((supertoken_graph G k s).neighborSet x) = k * d := by have e := Equiv.ofBijective (supertoken_graph_regular_of_degree_le_s_to_neighbor G k s hk x) ⟨supertoken_graph_regular_of_degree_le_s_to_neighbor_inj G k s hk x, supertoken_graph_regular_of_degree_le_s_to_neighbor_surj G k s hk x⟩ rw [← Fintype.card_congr e] rw [Fintype.card_sigma] simp_rw [SimpleGraph.card_neighborSet_eq_degree] simp_rw [hreg (x.1 _)] simp
The supertoken graph is regular of degree k * d.
The degree of x in the supertoken graph is by definition the cardinality of its neighbor set (SimpleGraph.card_neighborSet_eq_degree). Since this cardinality was shown to be k * d, the degree is k * d for every vertex x.
uses
SimpleGraph.card_neighborSet_eq_degreerw [← SimpleGraph.card_neighborSet_eq_degree] exact hcard
Finset.card_filter_le- The cardinality of a filtered sub-finset is at most the cardinality of the original finset.
supertoken_graph_regular_of_degree_le_s_card_filter_le_k- For any assignment of k tokens to vertices, the number of tokens placed at any specific vertex v is at most k.
supertoken_graph_regular_of_degree_le_s_card_filter_le_s- When k ≤ s, any configuration of k tokens places at most s tokens at any vertex v.
Function.update_self- Evaluating a function updated at a with value v at the input a returns v.
Function.update_of_ne- Evaluating a function updated at a' at a different input a ≠ a' leaves the value unchanged as f(a).
congr_arg- Applying a function to both sides of an equality preserves the equality.
Subtype.val- The projection extracting the underlying value from an element of a subtype.
supertoken_graph_regular_of_degree_le_s_to_neighbor- The map sending a token index i and a neighbor u of x(i) in G to the neighbor x[i ↦ u] of x in the supertoken graph.
Equiv.ofBijective- A bijective function between types induces an equivalence (bijection) of types.
supertoken_graph_regular_of_degree_le_s_to_neighbor_inj- The map from index-neighbor pairs to neighbors of x in the supertoken graph is injective.
supertoken_graph_regular_of_degree_le_s_to_neighbor_surj- The map from index-neighbor pairs to neighbors of x in the supertoken graph is surjective.
Fintype.card_congr- Equivalent finite types have the same cardinality.
Fintype.card_sigma- The cardinality of a sigma type is the sum over the index type of the cardinalities of the fibers.
SimpleGraph.card_neighborSet_eq_degree- The cardinality of the neighbor set of a vertex in a simple graph equals its degree.
- When k ≤ s, the capacity constraint that at most s tokens occupy any vertex is automatically satisfied by all configurations of k tokens, so the constraint plays no restrictive role in the graph's local degree.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma supertoken_graph_regular_of_degree_le_s_card_filter_le_k {V : Type*} [DecidableEq V] {k : ℕ} (x : Fin k → V) (v : V) : (Finset.univ.filter (fun i => x i = v)).card ≤ k := by have : (Finset.univ.filter (fun i => x i = v)).card ≤ (Finset.univ : Finset (Fin k)).card := Finset.card_filter_le _ _ simpa using thislemma supertoken_graph_regular_of_degree_le_s_card_filter_le_s {V : Type*} [DecidableEq V] {k s : ℕ} (hk : k ≤ s) (x : Fin k → V) (v : V) : (Finset.univ.filter (fun i => x i = v)).card ≤ s := (supertoken_graph_regular_of_degree_le_s_card_filter_le_k x v).trans hkdef supertoken_graph_regular_of_degree_le_s_to_neighbor {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (k s : ℕ) (hk : k ≤ s) (x : { x : Fin k → V // ∀ v : V, (Finset.univ.filter (fun i => x i = v)).card ≤ s }) (p : Σ (i : Fin k), G.neighborSet (x.1 i)) : (supertoken_graph G k s).neighborSet x := ⟨⟨Function.update x.1 p.1 p.2.1, supertoken_graph_regular_of_degree_le_s_card_filter_le_s hk _⟩, by dsimp [supertoken_graph] refine ⟨p.1, ?_, ?_⟩ · dsimp rw [Function.update_self] exact p.2.2 · intro j hj dsimp rw [Function.update_of_ne hj]⟩lemma supertoken_graph_regular_of_degree_le_s_to_neighbor_inj {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (k s : ℕ) (hk : k ≤ s) (x : { x : Fin k → V // ∀ v : V, (Finset.univ.filter (fun i => x i = v)).card ≤ s }) : Function.Injective (supertoken_graph_regular_of_degree_le_s_to_neighbor G k s hk x) := by rintro ⟨i₁, u₁, hu₁⟩ ⟨i₂, u₂, hu₂⟩ h have hfn : Function.update x.1 i₁ u₁ = Function.update x.1 i₂ u₂ := by have h1 := congr_arg Subtype.val h exact congr_arg Subtype.val h1 have h_ne1 : u₁ ≠ x.1 i₁ := by intro heq have hadj : G.Adj (x.1 i₁) u₁ := hu₁ rw [heq] at hadj exact hadj.ne rfl have hi : i₁ = i₂ := by by_contra hne have h1 : Function.update x.1 i₁ u₁ i₁ = Function.update x.1 i₂ u₂ i₁ := by rw [hfn] simp only [Function.update_self] at h1 rw [Function.update_of_ne hne] at h1 exact h_ne1 h1 subst hi have hu : u₁ = u₂ := by have h1 : Function.update x.1 i₁ u₁ i₁ = Function.update x.1 i₁ u₂ i₁ := by rw [hfn] simp only [Function.update_self] at h1 exact h1 subst hu rfllemma supertoken_graph_regular_of_degree_le_s_to_neighbor_surj {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (k s : ℕ) (hk : k ≤ s) (x : { x : Fin k → V // ∀ v : V, (Finset.univ.filter (fun i => x i = v)).card ≤ s }) : Function.Surjective (supertoken_graph_regular_of_degree_le_s_to_neighbor G k s hk x) := by rintro ⟨y, hy⟩ obtain ⟨i, hadj, heq⟩ := hy have hu : y.1 i ∈ G.neighborSet (x.1 i) := hadj refine ⟨⟨i, ⟨y.1 i, hu⟩⟩, ?_⟩ ext1 ext1 ext j dsimp [supertoken_graph_regular_of_degree_le_s_to_neighbor] by_cases hji : j = i · subst hji rw [Function.update_self] · rw [Function.update_of_ne hji] exact heq j hjiopen scoped Classical in/-- The supertoken graph of a d-regular graph with k ≤ s tokens is regular of degree kd. -/theorem supertoken_graph_regular_of_degree_le_s {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (d : ℕ) (hreg : G.IsRegularOfDegree d) (s : ℕ) (k : ℕ) (hk : k ≤ s) : (supertoken_graph G k s).IsRegularOfDegree (k * d) := by intro x have hcard : Fintype.card ((supertoken_graph G k s).neighborSet x) = k * d := by have e := Equiv.ofBijective (supertoken_graph_regular_of_degree_le_s_to_neighbor G k s hk x) ⟨supertoken_graph_regular_of_degree_le_s_to_neighbor_inj G k s hk x, supertoken_graph_regular_of_degree_le_s_to_neighbor_surj G k s hk x⟩ rw [← Fintype.card_congr e] rw [Fintype.card_sigma] simp_rw [SimpleGraph.card_neighborSet_eq_degree] simp_rw [hreg (x.1 _)] simp rw [← SimpleGraph.card_neighborSet_eq_degree] exact hcard