AFTD Auto-Formalizing Theoretical Domains

supertoken_graph_regular_of_degree_le_s

theoremverified

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.

  1. 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.

    lines 1–12

    uses Finset.card_filter_le, supertoken_graph_regular_of_degree_le_s_card_filter_le_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 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
    
  2. 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).

    lines 13–27

    uses supertoken_graph_regular_of_degree_le_s_card_filter_le_s, Function.update_self, Function.update_of_ne

    def 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]⟩
    
  3. 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₁).

    lines 28–40

    uses congr_arg, Subtype.val

    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
  4. 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₂.

    lines 41–47

    uses Function.update_self, Function.update_of_ne

      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
  5. 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.

    lines 48–54

    uses Function.update_self

      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
      rfl
    
  6. 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.

    lines 55–72

    uses supertoken_graph_regular_of_degree_le_s_to_neighbor, Function.update_self, Function.update_of_ne

    lemma 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
    
  7. 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.

    lines 73–88

    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_degree

    open 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
  8. 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.

    lines 89–90

    uses SimpleGraph.card_neighborSet_eq_degree

      rw [← 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.

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

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
See it in the graphDiscuss this resultChallenge it