simple_graph_t_chromatic_ps_eval_one
For any finite simple graph G on a finite vertex type V and any natural number n, evaluating the n-th principal specialization of the t-chromatic symmetric function ps_n(Z_G(x; t)) at t = 1 via Polynomial.eval 1 yields the n-th principal specialization of the chromatic symmetric function ps_n(X_G(x)).
Statement
theorem simple_graph_t_chromatic_ps_eval_one {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) : Polynomial.eval 1 (simple_graph_t_chromatic_principal_specialization G n) = simple_graph_chromatic_principal_specialization G n
- Source
- arXiv:2610.31785, proof of Proposition 3.9
- 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_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 chromatic symmetric…
- Used by 1
- simple_graph_t_chromatic_ps_determines_chromatic_psLet G and H be finite simple graphs on finite vertex types V and W, respectively, and let n be a positive integer. If the n-th principal…
Read back from the Lean
For any finite type $V$, any simple graph $G$ on $V$, and any natural number $n$, evaluating the $t$-chromatic principal specialization polynomial of $G$ with $n$ colors at $t = 1$ yields the chromatic principal specialization polynomial of $G$ with $n$ colors.
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
The proof proceeds by expanding the definitions of both principal specializations as sums of monomials indexed by proper colorings of $G$. Because polynomial evaluation at $t = 1$ is a ring homomorphism, it distributes across the finite sum. Finally, evaluating each monomial $t^{|\mathrm{im}(c)|} q^{\sum_{v} c(v)}$ at $t = 1$ leaves $q^{\sum_{v} c(v)}$, matching the chromatic principal specialization term by term.
The goal is rewritten in terms of the explicit sums defining both principal specializations.
Unfolding the definitions of `simple_graph_t_chromatic_principal_specialization` and `simple_graph_chromatic_principal_specialization` expresses both sides as sums over all proper vertex colorings $c : V \to \{0, \dots, n-1\}$. On the left, each coloring contributes $t^{|\mathrm{im}(c)|} q^{\sum_v c(v)}$ inside an evaluation at $t = 1$; on the right, each coloring contributes $q^{\sum_v c(v)}$.
uses
simple_graph_t_chromatic_principal_specialization,simple_graph_chromatic_principal_specializationsimp only [simple_graph_t_chromatic_principal_specialization, simple_graph_chromatic_principal_specialization]Evaluation at $t = 1$ distributes across the sum over proper colorings.
Because polynomial evaluation at $1$ definitionally coincides with the ring homomorphism `Polynomial.evalRingHom 1` (recorded as hypothesis $h$), it preserves addition and commutes with finite sums via `map_sum`, moving the evaluation inside the sum onto each individual summand.
uses
map_sumhave h : ∀ p : Polynomial (Polynomial ℕ), Polynomial.eval (1 : Polynomial ℕ) p = Polynomial.evalRingHom 1 p := fun p => rfl rw [h, map_sum]
Evaluating each monomial at $t = 1$ yields the chromatic principal specialization.
Each summand on the left is a monomial of the form $a \cdot t^k$, where $a = q^{\sum_v c(v)}$ and $k = |\mathrm{im}(c)|$. Applying `Polynomial.eval_monomial` evaluates $a \cdot t^k$ at $t = 1$ to $a \cdot 1^k = a$, reducing the left-hand sum to the right-hand sum and closing the goal.
uses
Polynomial.eval_monomialsimp [Polynomial.eval_monomial]
simple_graph_t_chromatic_principal_specialization- The $n$-th principal specialization of the $t$-chromatic symmetric function of $G$, defined as $\sum_c t^{|\mathrm{im}(c)|} q^{\sum_{v} c(v)}$ over proper colorings $c : V \to \{0, \dots, n-1\}$.
simple_graph_chromatic_principal_specialization- The $n$-th principal specialization of the chromatic symmetric function of $G$, defined as $\sum_c q^{\sum_{v} c(v)}$ over proper colorings $c : V \to \{0, \dots, n-1\}$.
map_sum- An additive monoid homomorphism respects finite sums: $g(\sum_{x \in s} f(x)) = \sum_{x \in s} g(f(x))$.
Polynomial.eval_monomial- Evaluating a monomial $a \cdot X^n$ at $x$ yields $a \cdot x^n$.
- In Lean, bivariate polynomials in $q$ and $t$ are formalized as iterated univariate polynomials $\mathrm{Polynomial}\ (\mathrm{Polynomial}\ \mathbb{N})$, where $t$ is the indeterminate of the outer polynomial and its coefficients are polynomials in $q$. To move the evaluation at $t = 1$ inside the finite sum over colorings, the proof notes that `Polynomial.eval 1` is definitionally the ring homomorphism `Polynomial.evalRingHom 1`, which allows applying `map_sum`.
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.
/-- Evaluating the n-th principal specialization ps_n(Z_G(x; t)) at t = 1 yields ps_n(X_G(x)). -/theorem simple_graph_t_chromatic_ps_eval_one {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) : Polynomial.eval 1 (simple_graph_t_chromatic_principal_specialization G n) = simple_graph_chromatic_principal_specialization G n := by simp only [simple_graph_t_chromatic_principal_specialization, simple_graph_chromatic_principal_specialization] have h : ∀ p : Polynomial (Polynomial ℕ), Polynomial.eval (1 : Polynomial ℕ) p = Polynomial.evalRingHom 1 p := fun p => rfl rw [h, map_sum] simp [Polynomial.eval_monomial]