supertoken_graph_bipartite
Let G be a finite bipartite simple graph on vertex type V with decidable equality (satisfying G.IsBipartite). Let s ≥ 1 and 1 ≤ k ≤ s * Fintype.card V. Then the supertoken graph supertoken_graph G k s is bipartite (satisfies SimpleGraph.IsBipartite).
Statement
theorem supertoken_graph_bipartite {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) (hG : G.IsBipartite) (s : ℕ) (hs : 1 ≤ s) (k : ℕ) (hk1 : 1 ≤ k) (hk2 : k ≤ s * Fintype.card V) : (supertoken_graph G k s).IsBipartite
- Formalizes
- arXiv:2611.06275 Theorem 2.5 -- On generalized k-token graphs with distinguishable tokens and a maximum capacity of s tokens per vertex
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
Read back from the Lean
Let $V$ be a finite type with decidable equality, and let $G$ be a bipartite simple graph on $V$. Let $s$ and $k$ be natural numbers such that $1 \le s$, $1 \le k$, and $k \le s \cdot |V|$. Then the supertoken graph of $G$ with parameters $k$ and $s$, supertoken_graph G k s, is bipartite.
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 prove that the supertoken graph is bipartite, choose a bipartition (S, T) of the underlying graph G and 2-color configurations according to the parity of the number of tokens placed on S. Since an adjacent configuration differs by moving exactly one token along an edge of G, that token crosses between S and T while all other tokens remain in place. Consequently, the token count on S changes by ±1, flipping the parity and ensuring that every edge connects an even configuration to an odd configuration.
The number of tokens of configuration x in S decomposes into the contribution of coordinate i and the count over all other coordinates.
The universe of indices is rewritten as the union of {i} and the remaining indices using Finset.insert_erase and Finset.mem_univ. Filtering this set distributes across insertion via Finset.filter_insert. A case split on whether x i ∈ S resolves the cardinality: if true, Finset.card_insert_of_notMem and if_pos show the size increases by 1, with omega simplifying the sum; if false, simp reduces the count to that of the remaining coordinates plus 0.
uses
Finset.insert_erase,Finset.mem_univ,Finset.filter_insert,if_pos,Finset.card_insert_of_notMemconv_lhs => rw [← Finset.insert_erase (Finset.mem_univ i)] rw [Finset.filter_insert] by_cases hp : x i ∈ S · rw [if_pos hp, Finset.card_insert_of_notMem (by simp), if_pos hp] omega · simp [hp]
For configurations x and y agreeing on all coordinates except i, the token counts in S on the remaining coordinates are equal.
Decompose the token counts in S for x and y at coordinate i using supertoken_graph_bipartite_count_split. For any coordinate j distinct from i, the configurations satisfy x j = y j by hypothesis, using Finset.ne_of_mem_erase. Congruence of filtering with Finset.filter_congr then shows that the filtered sub-finsets on indices other than i are identical, so their cardinalities coincide.
uses
supertoken_graph_bipartite_count_split,Finset.filter_congr,Finset.ne_of_mem_erasehave hx := supertoken_graph_bipartite_count_split S x i have hy := supertoken_graph_bipartite_count_split S y i have hrest : ((Finset.univ.erase i).filter (fun j => y j ∈ S)).card = ((Finset.univ.erase i).filter (fun j => x j ∈ S)).card := by congr 1 apply Finset.filter_congr intro j hj rw [hxy j (Finset.ne_of_mem_erase hj)]
If two configurations differ only at coordinate i and that token crosses the boundary of S, the sum of their token counts in S is odd.
Substitute the count splittings of x and y and the equality of counts on the remaining indices. The sum becomes the sum of the two indicators at coordinate i plus twice the count on the remaining coordinates. Since the token at i crosses S, one configuration has its token in S and the other does not (analyzed via if_pos and if_neg), so the sum of the indicators is 1. The total sum is therefore 2 * (count on the rest) + 1, which ring arithmetic proves is odd.
uses
if_pos,if_negrw [hx, hy, hrest] obtain ⟨ha, hb⟩ | ⟨ha, hb⟩ := h · rw [if_pos ha, if_neg hb] exact ⟨_, by ring⟩ · rw [if_neg ha, if_pos hb] exact ⟨_, by ring⟩
To show the supertoken graph is bipartite, it suffices to show that configurations with an even number of tokens in S and those with an odd number of tokens in S form a valid bipartition.
Since the base graph G is bipartite, let (S, T) be a bipartition of G. Define a 2-coloring of the configurations by the parity of the number of tokens lying in S. By SimpleGraph.IsBipartiteWith.isBipartite, proving the supertoken graph is bipartite reduces to showing that the even and odd configuration classes are disjoint and that every edge connects an even configuration to an odd configuration.
uses
SimpleGraph.IsBipartiteWith.isBipartiteclassical obtain ⟨S, T, hST⟩ := hG.exists_isBipartiteWith -- Parity colouring: the parity of the number of tokens on the part `S`. let cnt : (Fin k → V) → ℕ := fun x => (Finset.univ.filter (fun i => x i ∈ S)).card refine SimpleGraph.IsBipartiteWith.isBipartite (s := {x | Even (cnt x.1)}) (t := {x | Odd (cnt x.1)}) ⟨?_, ?_⟩
The set of even configurations and the set of odd configurations are disjoint.
Rewriting disjointness via Set.disjoint_left, suppose a configuration had a token count in S that was both even and odd. By Nat.not_even_iff_odd.mpr, an odd natural number is not even, yielding an immediate contradiction.
uses
Set.disjoint_left,Nat.not_even_iff_odd.mpr· rw [Set.disjoint_left] intro x hx hx' exact (Nat.not_even_iff_odd.mpr hx') hx
Along any edge of the supertoken graph, the single moved token crosses between S and its complement.
An edge between configurations x and y corresponds to moving a single token at some coordinate i along an edge of G while leaving all other coordinates unchanged. Because (S, T) is a bipartition of G, the edge has one endpoint in S and the other in T. Since S and T are disjoint (Set.disjoint_right.mp), an endpoint in T cannot be in S. Thus, either x i ∈ S and y i ∉ S (via Or.inl), or x i ∉ S and y i ∈ S (via Or.inr).
uses
Or.inl,Or.inr,Set.disjoint_right.mp· rintro x y ⟨i, hi, hxy⟩ -- the unique moved token crosses the bipartition, so it lies in `S` on exactly one side have hm := hST.mem_of_adj hi have hmem : (x.1 i ∈ S ∧ y.1 i ∉ S) ∨ (x.1 i ∉ S ∧ y.1 i ∈ S) := by obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hm · exact Or.inl ⟨h1, Set.disjoint_right.mp hST.disjoint h2⟩ · exact Or.inr ⟨Set.disjoint_right.mp hST.disjoint h1, h2⟩The sum of the token counts in S for adjacent configurations is odd, so one count is odd if and only if the other is even.
Applying supertoken_graph_bipartite_count_odd to x, y, and the crossing coordinate i shows that the sum of their token counts in S is odd. By Nat.odd_add.mp, the sum of two natural numbers is odd if and only if their parities are opposite.
uses
supertoken_graph_bipartite_count_odd,Nat.odd_add.mphave hodd := supertoken_graph_bipartite_count_odd x.1 y.1 i hxy hmem have hn := Nat.odd_add.mp hodd
Every edge of the supertoken graph connects an even configuration to an odd configuration.
Split into cases on whether the token count in S for x is even. If it is even, it is not odd (by Nat.not_even_iff_odd.mpr), so the parity equivalence implies the count for y is not even, meaning by Nat.not_even_iff_odd.mp that y is odd. If x is not even, then by Nat.not_even_iff_odd.mp it is odd, and the parity equivalence directly implies that y is even. In either case, the edge connects an even configuration to an odd configuration.
uses
Nat.not_even_iff_odd.mpr,Nat.not_even_iff_odd.mpby_cases hcx : Even (cnt x.1) · left refine ⟨hcx, ?_⟩ have hno : ¬ Odd (cnt x.1) := fun h => (Nat.not_even_iff_odd.mpr h) hcx exact Nat.not_even_iff_odd.mp (fun h => hno (hn.mpr h)) · right refine ⟨Nat.not_even_iff_odd.mp hcx, ?_⟩ exact hn.mp (Nat.not_even_iff_odd.mp hcx)
Finset.insert_erase- Inserting an element a into a finset s with a removed recovers s, provided a ∈ s.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
Finset.filter_insert- Filtering an inserted finset conditionally inserts the element depending on whether it satisfies the predicate.
if_pos- An if-then-else expression evaluates to the then-branch when the condition is true.
Finset.card_insert_of_notMem- Inserting an element not belonging to a finset increases its cardinality by 1.
supertoken_graph_bipartite_count_split- The number of tokens of a configuration lying in S splits into the indicator of whether the i-th coordinate lies in S plus the number of remaining tokens in S.
Finset.filter_congr- Two filtered finsets are equal if their filtering predicates are equivalent on all elements of the finset.
Finset.ne_of_mem_erase- An element belonging to a finset with a removed is not equal to a.
if_neg- An if-then-else expression evaluates to the else-branch when the condition is false.
SimpleGraph.IsBipartiteWith.isBipartite- A graph that admits a bipartition into two subsets is bipartite.
Set.disjoint_left- Two sets are disjoint if and only if no element belongs to both.
Nat.not_even_iff_odd.mpr- If a natural number is odd, then it is not even.
Or.inl- First disjunct injection for a logical disjunction.
Or.inr- Second disjunct injection for a logical disjunction.
Set.disjoint_right.mp- If two sets are disjoint, any element in the second does not belong to the first.
supertoken_graph_bipartite_count_odd- If two configurations differ only at coordinate i and that token crosses the boundary of S, the total number of tokens in S across both configurations is odd.
Nat.odd_add.mp- The sum of two natural numbers is odd if and only if one is odd and the other is even.
Nat.not_even_iff_odd.mp- If a natural number is not even, then it is odd.
- The formal proof establishes two helper lemmas (`supertoken_graph_bipartite_count_split` and `supertoken_graph_bipartite_count_odd`) to handle the combinatorial count and parity change before proving the main theorem.
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.
/-- Splitting the number of tokens of a configuration lying in `S` off at a single coordinate. -/private lemma supertoken_graph_bipartite_count_split {V : Type*} (S : Set V) [DecidablePred (· ∈ S)] {k : ℕ} (x : Fin k → V) (i : Fin k) : (Finset.univ.filter (fun j => x j ∈ S)).card = (if x i ∈ S then 1 else 0) + ((Finset.univ.erase i).filter (fun j => x j ∈ S)).card := by conv_lhs => rw [← Finset.insert_erase (Finset.mem_univ i)] rw [Finset.filter_insert] by_cases hp : x i ∈ S · rw [if_pos hp, Finset.card_insert_of_notMem (by simp), if_pos hp] omega · simp [hp]/-- If two configurations differ only at a coordinate `i` whose token crosses `S` in one direction,then the total number of tokens lying in `S` over the two configurations is odd. -/private lemma supertoken_graph_bipartite_count_odd {V : Type*} {k : ℕ} {S : Set V} [DecidablePred (· ∈ S)] (x y : Fin k → V) (i : Fin k) (hxy : ∀ j, j ≠ i → x j = y j) (h : (x i ∈ S ∧ y i ∉ S) ∨ (x i ∉ S ∧ y i ∈ S)) : Odd ((Finset.univ.filter (fun j => x j ∈ S)).card + (Finset.univ.filter (fun j => y j ∈ S)).card) := by have hx := supertoken_graph_bipartite_count_split S x i have hy := supertoken_graph_bipartite_count_split S y i have hrest : ((Finset.univ.erase i).filter (fun j => y j ∈ S)).card = ((Finset.univ.erase i).filter (fun j => x j ∈ S)).card := by congr 1 apply Finset.filter_congr intro j hj rw [hxy j (Finset.ne_of_mem_erase hj)] rw [hx, hy, hrest] obtain ⟨ha, hb⟩ | ⟨ha, hb⟩ := h · rw [if_pos ha, if_neg hb] exact ⟨_, by ring⟩ · rw [if_neg ha, if_pos hb] exact ⟨_, by ring⟩/-- Theorem 2.5: If G is bipartite, then F^s_{k x 1}(G) is bipartite for every admissible k, s. -/theorem supertoken_graph_bipartite {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) (hG : G.IsBipartite) (s : ℕ) (hs : 1 ≤ s) (k : ℕ) (hk1 : 1 ≤ k) (hk2 : k ≤ s * Fintype.card V) : (supertoken_graph G k s).IsBipartite := by classical obtain ⟨S, T, hST⟩ := hG.exists_isBipartiteWith -- Parity colouring: the parity of the number of tokens on the part `S`. let cnt : (Fin k → V) → ℕ := fun x => (Finset.univ.filter (fun i => x i ∈ S)).card refine SimpleGraph.IsBipartiteWith.isBipartite (s := {x | Even (cnt x.1)}) (t := {x | Odd (cnt x.1)}) ⟨?_, ?_⟩ · rw [Set.disjoint_left] intro x hx hx' exact (Nat.not_even_iff_odd.mpr hx') hx · rintro x y ⟨i, hi, hxy⟩ -- the unique moved token crosses the bipartition, so it lies in `S` on exactly one side have hm := hST.mem_of_adj hi have hmem : (x.1 i ∈ S ∧ y.1 i ∉ S) ∨ (x.1 i ∉ S ∧ y.1 i ∈ S) := by obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hm · exact Or.inl ⟨h1, Set.disjoint_right.mp hST.disjoint h2⟩ · exact Or.inr ⟨Set.disjoint_right.mp hST.disjoint h1, h2⟩ have hodd := supertoken_graph_bipartite_count_odd x.1 y.1 i hxy hmem have hn := Nat.odd_add.mp hodd by_cases hcx : Even (cnt x.1) · left refine ⟨hcx, ?_⟩ have hno : ¬ Odd (cnt x.1) := fun h => (Nat.not_even_iff_odd.mpr h) hcx exact Nat.not_even_iff_odd.mp (fun h => hno (hn.mpr h)) · right refine ⟨Nat.not_even_iff_odd.mp hcx, ?_⟩ exact hn.mp (Nat.not_even_iff_odd.mp hcx)