simple_graph_t_chromatic_ps_min_add_max_q_degree
For a finite simple graph G and n ∈ ℕ, if d and D are the least and greatest exponents j of q such that some coefficient of t^k q^j in ps_n(Z_G(x; t)) is nonzero, then (n-1)|V| = d + D.
Statement
theorem simple_graph_t_chromatic_ps_min_add_max_q_degree {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (d D : ℕ) (hd : IsLeast {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} d) (hD : IsGreatest {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} D) : (n - 1) * Fintype.card V = d + D
- Source
- arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16(1), the step (n-1)|V| = d + D
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_t_chromatic_principal_specializationFor a finite simple graph G on a finite vertex type V and a natural number n, the n-th principal specialization of the t-chromatic…
- simple_graph_t_chromatic_ps_coeff_coeffFor a finite simple graph G and natural numbers n, k, j, the coefficient of t^k q^j in the n-th principal specialization ps_n(Z_G(x; t))…
- Used by 2
- simple_graph_t_chromatic_ps_q_coeff_symmLet n ≥ 2 and let G be a finite simple graph with at least 2 vertices that has a proper coloring with n colors. Let d and D be the minimum…
- simple_graph_t_chromatic_ps_vertex_count_eqLet n ≥ 2 and let G be a finite simple graph with at least 2 vertices that has a proper coloring with n colors (χ_G(n) > 0). Let d and D…
The proof, explained
The theorem characterizes the q-degrees appearing with nonzero coefficient in the principal specialization as the vertex color sums ∑_{v ∈ V} c(v) of proper n-colorings c. Color reversal i ↦ n - 1 - i defines an involution on proper colorings such that the sum of the color sum of any coloring c and that of its reversal r(c) is identically (n - 1)|V|. Applying this identity to a coloring c0 achieving the minimal sum d shows that (n - 1)|V| - d ≤ D, while applying it to a coloring c1 achieving the maximal sum D shows that d ≤ (n - 1)|V| - D, which together force (n - 1)|V| = d + D.
An exponent j of q appears with nonzero coefficient in the principal specialization if and only if there exists a proper n-coloring c of G with color sum ∑ v, c(v) = j.
Using the coefficient formula for the principal specialization (`simple_graph_t_chromatic_ps_coeff_coeff`), the condition that some coefficient is nonzero is rewritten via `Fintype.card_eq_zero_iff` and `not_isEmpty_iff` to the nonemptiness of the set of colorings with image size k and color sum j. The forward direction discards the image size k, while the reverse direction takes k to be the cardinality of the image of c.
uses
Set.mem_setOf_eq,simple_graph_t_chromatic_ps_coeff_coeff,ne_eq,Fintype.card_eq_zero_iff,not_isEmpty_iffsimp only [Set.mem_setOf_eq, simple_graph_t_chromatic_ps_coeff_coeff, ne_eq, Fintype.card_eq_zero_iff, not_isEmpty_iff] constructor · rintro ⟨k, ⟨c, -, hc⟩⟩; exact ⟨c, hc⟩ · rintro ⟨c, hc⟩; exact ⟨_, ⟨c, rfl, hc⟩⟩
There exist proper n-colorings c0 and c1 of G whose color sums are d and D, respectively.
Because d is the least element and D is the greatest element of the set of non-vanishing q-exponents, both d and D belong to this set. Applying the forward direction of `simple_graph_t_chromatic_ps_min_add_max_q_degree_mem` produces proper colorings c0 with sum d and c1 with sum D.
uses
simple_graph_t_chromatic_ps_min_add_max_q_degree_memclassical obtain ⟨c0, hc0⟩ := (simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n d).1 hd.1 obtain ⟨c1, hc1⟩ := (simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n D).1 hD.1
Color reversal r(c)(v) = rev(c(v)) defines an operation sending any proper n-coloring of G to another proper n-coloring of G.
Assigning each vertex v the reversed color Fin.rev(c(v)) via `SimpleGraph.Coloring.mk` produces a valid coloring because Fin.rev is injective (`Fin.rev_injective`), so adjacent vertices with distinct colors in c remain assigned distinct colors in r(c).
uses
SimpleGraph.Coloring.mk,Fin.rev,Fin.rev_injectivelet r : G.Coloring (Fin n) → G.Coloring (Fin n) := fun c => SimpleGraph.Coloring.mk (fun v => Fin.rev (c v)) (fun h e => c.valid h (Fin.rev_injective e))
For any proper n-coloring c of G, the sum of the color sum of r(c) and the color sum of c equals (n - 1)|V|.
Combining the two vertex sums via `Finset.sum_add_distrib`, at each vertex v the sum of the reversed color and original color is (n - 1 - c(v)) + c(v) = n - 1 by `Fin.val_rev` and `Fin.isLt`. Summing this constant value n - 1 over all vertices in V gives (n - 1)|V| using `Finset.sum_const`, `Finset.card_univ`, and `smul_eq_mul`.
uses
Finset.sum_add_distrib,Fin.val_rev,Fin.isLt,Finset.sum_const,Finset.card_univ,smul_eq_mulhave hW : ∀ c : G.Coloring (Fin n), ∑ v : V, ((r c) v : ℕ) + ∑ v : V, (c v : ℕ) = (n - 1) * Fintype.card V := by intro c rw [← Finset.sum_add_distrib] have : ∀ v, ((r c) v : ℕ) + (c v : ℕ) = n - 1 := by intro v show ((Fin.rev (c v) : Fin n) : ℕ) + (c v : ℕ) = n - 1 rw [Fin.val_rev]; have := (c v).isLt; omega simp only [this, Finset.sum_const, Finset.card_univ, smul_eq_mul] ring
The color sums of r(c0) and r(c1) satisfy ∑ v, r(c0)(v) ≤ D and d ≤ ∑ v, r(c1)(v), while summing each with d and D respectively gives (n - 1)|V|.
Since r(c0) and r(c1) are proper colorings, their color sums belong to the set of non-vanishing q-exponents by `simple_graph_t_chromatic_ps_min_add_max_q_degree_mem`. Because D is greatest and d is least, ∑ v, r(c0)(v) ≤ D and d ≤ ∑ v, r(c1)(v). Furthermore, the coloring sum identity hW applied to c0 and c1 yields ∑ v, r(c0)(v) + d = (n - 1)|V| and ∑ v, r(c1)(v) + D = (n - 1)|V|.
uses
simple_graph_t_chromatic_ps_min_add_max_q_degree_memhave h1 := hD.2 ((simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n _).2 ⟨r c0, rfl⟩) have h2 := hd.2 ((simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n _).2 ⟨r c1, rfl⟩) have e0 := hW c0 have e1 := hW c1
(n - 1)|V| = d + D. automation
Linear arithmetic over ℕ (`omega`) combines ∑ v, r(c0)(v) + d = (n - 1)|V| with ∑ v, r(c0)(v) ≤ D to give (n - 1)|V| ≤ d + D, and combines ∑ v, r(c1)(v) + D = (n - 1)|V| with d ≤ ∑ v, r(c1)(v) to give d + D ≤ (n - 1)|V|, forcing equality.
omega
Set.mem_setOf_eq- An element x belongs to the set {y | p y} if and only if p x holds.
simple_graph_t_chromatic_ps_coeff_coeff- The coefficient of t^k q^j in the principal specialization ps_n(Z_G) is the number of proper n-colorings of G whose image has cardinality k and whose color sum is j.
ne_eq- The inequality a ≠ b is defined as the negation of a = b.
Fintype.card_eq_zero_iff- The cardinality of a finite type is zero if and only if the type is empty.
not_isEmpty_iff- A type is not empty if and only if it is nonempty.
simple_graph_t_chromatic_ps_min_add_max_q_degree_mem- An exponent j appears with a nonzero coefficient in the principal specialization if and only if there exists a proper n-coloring of G with color sum j.
SimpleGraph.Coloring.mk- Constructs a proper coloring of a graph from a vertex coloring function and a proof that adjacent vertices receive different colors.
Fin.rev- The reversal permutation on Fin n, mapping each element i to n - 1 - i.
Fin.rev_injective- The reversal function on Fin n is injective.
Finset.sum_add_distrib- The sum of a pointwise sum of two functions over a finite set equals the sum of their individual sums.
Fin.val_rev- The numerical value of the reversed element rev(i) in Fin n is n - (i + 1).
Fin.isLt- The numerical value of an element of Fin n is strictly less than n.
Finset.sum_const- The sum of a constant value over a finite set equals the cardinality of the set times that value.
Finset.card_univ- The cardinality of the universal finset of a finite type is the cardinality of the type.
smul_eq_mul- Scalar multiplication of natural numbers coincides with ordinary multiplication.
- The final step relies on the `omega` decision procedure for Presburger arithmetic to deduce the equality (n - 1)|V| = d + D from the two opposing inequalities (n - 1)|V| - d ≤ D and d ≤ (n - 1)|V| - D over ℕ.
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.
theorem simple_graph_t_chromatic_ps_min_add_max_q_degree_mem {V : Type*} [Fintype V] (G : SimpleGraph V) (n j : ℕ) : j ∈ {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} ↔ ∃ c : G.Coloring (Fin n), ∑ v : V, (c v : ℕ) = j := by simp only [Set.mem_setOf_eq, simple_graph_t_chromatic_ps_coeff_coeff, ne_eq, Fintype.card_eq_zero_iff, not_isEmpty_iff] constructor · rintro ⟨k, ⟨c, -, hc⟩⟩; exact ⟨c, hc⟩ · rintro ⟨c, hc⟩; exact ⟨_, ⟨c, rfl, hc⟩⟩theorem simple_graph_t_chromatic_ps_min_add_max_q_degree {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (d D : ℕ) (hd : IsLeast {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} d) (hD : IsGreatest {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} D) : (n - 1) * Fintype.card V = d + D := by classical obtain ⟨c0, hc0⟩ := (simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n d).1 hd.1 obtain ⟨c1, hc1⟩ := (simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n D).1 hD.1 let r : G.Coloring (Fin n) → G.Coloring (Fin n) := fun c => SimpleGraph.Coloring.mk (fun v => Fin.rev (c v)) (fun h e => c.valid h (Fin.rev_injective e)) have hW : ∀ c : G.Coloring (Fin n), ∑ v : V, ((r c) v : ℕ) + ∑ v : V, (c v : ℕ) = (n - 1) * Fintype.card V := by intro c rw [← Finset.sum_add_distrib] have : ∀ v, ((r c) v : ℕ) + (c v : ℕ) = n - 1 := by intro v show ((Fin.rev (c v) : Fin n) : ℕ) + (c v : ℕ) = n - 1 rw [Fin.val_rev]; have := (c v).isLt; omega simp only [this, Finset.sum_const, Finset.card_univ, smul_eq_mul] ring have h1 := hD.2 ((simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n _).2 ⟨r c0, rfl⟩) have h2 := hd.2 ((simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n _).2 ⟨r c1, rfl⟩) have e0 := hW c0 have e1 := hW c1 omega