simple_graph_t_chromatic_ps_coeff_coeff
For 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)) (simple_graph_t_chromatic_principal_specialization G n, outer variable t, inner variable q) equals the number of proper colorings c : V → Fin n that use exactly k distinct colors and have weight ∑_v c(v) = j.
Statement
theorem simple_graph_t_chromatic_ps_coeff_coeff {V : Type*} [Fintype V] (G : SimpleGraph V) (n k j : ℕ) : ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j = Fintype.card {c : G.Coloring (Fin n) // (Finset.univ.image c).card = k ∧ ∑ v : V, (c v : ℕ) = j}
- Source
- arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16 (equation (3.1): the coefficients count proper colorings by number of colors and weight)
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 2
- simple_graph_t_chromatic_ps_min_add_max_q_degreeFor 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…
- 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…
The proof, explained
The proof shows that extracting the coefficient of t^k q^j from the principal specialization counts proper colorings with exactly k colors and total weight j. It expands the specialization into a sum of monomials t^(|c(V)|) q^(∑_v c(v)) over colorings c and moves the coefficient extractions inside the sum. Simultaneously, it rewrites the cardinality on the right-hand side as a sum of 1s over matching colorings, reducing the goal by sum congruence to verifying term-by-term equality for each coloring via a straightforward case split.
The coefficient [t^k q^j] of the principal specialization equals the sum over all proper colorings c of the coefficient [q^j] of (if |c(V)| = k then q^(∑_v c(v)) else 0).
Unfolding the definition of the principal specialization shows it is a sum over all proper n-colorings c of the bivariate monomial t^(|c(V)|) q^(∑_v c(v)). Applying `Polynomial.finsetSum_coeff` twice moves the coefficient extractions for t (degree k) and q (degree j) inside the sum over colorings. Then `Polynomial.coeff_monomial` evaluates the outer coefficient with respect to t, leaving an indicator (if |c(V)| = k then q^(∑_v c(v)) else 0).
uses
Polynomial.finsetSum_coeff,Polynomial.coeff_monomialclassical unfold simple_graph_t_chromatic_principal_specialization rw [Polynomial.finsetSum_coeff, Polynomial.finsetSum_coeff] simp only [Polynomial.coeff_monomial]
The right-hand side, counting colorings using k colors with total weight j, can be written as the sum over all colorings of an indicator function for those two conditions.
By `Fintype.card_subtype`, the cardinality of the subtype is the cardinality of the corresponding filtered set of colorings. Writing this cardinality as a sum of ones via `Finset.card_eq_sum_ones` and transforming the filter into an if-then-else condition via `Finset.sum_filter`, the right-hand side becomes the sum over all colorings c of (if |c(V)| = k ∧ ∑_v c(v) = j then 1 else 0).
uses
Fintype.card_subtype,Finset.card_eq_sum_ones,Finset.sum_filterrw [Fintype.card_subtype] rw [Finset.card_eq_sum_ones, Finset.sum_filter]
It suffices to show that the summands on both sides are equal for each individual coloring c.
Using `Finset.sum_congr`, since both sides are sums over the universal set of colorings, equality of the entire sums follows if the summands agree for every coloring c.
uses
Finset.sum_congrrefine Finset.sum_congr rfl (fun c _ => ?_)
For every coloring c, the contribution from the polynomial equals the indicator function testing whether |c(V)| = k and ∑_v c(v) = j.
We split into four cases depending on whether |c(V)| = k holds and whether ∑_v c(v) = j holds. In all four cases, simplifying with the case hypotheses and `Polynomial.coeff_monomial` shows both sides evaluate to 1 when both conditions are satisfied, and to 0 otherwise.
uses
Polynomial.coeff_monomialby_cases h1 : (Finset.univ.image c).card = k <;> by_cases h2 : ∑ v : V, (c v : ℕ) = j <;> simp [h1, h2, Polynomial.coeff_monomial]
Polynomial.finsetSum_coeff- The coefficient of degree n of a finite sum of polynomials is the sum of their degree-n coefficients: [Xⁿ] (∑ᵢ f(i)) = ∑ᵢ ([Xⁿ] f(i)).
Polynomial.coeff_monomial- The coefficient of degree m of the monomial a Xⁿ is a if n = m and 0 otherwise.
Fintype.card_subtype- The cardinality of a subtype {x // p x} is equal to the cardinality of the filtered finset of elements satisfying p.
Finset.card_eq_sum_ones- The cardinality of a finite set s equals the sum of 1 over all elements of s.
Finset.sum_filter- Summing a function f over elements satisfying a predicate p equals summing (if p(a) then f(a) else 0) over the entire finite set.
Finset.sum_congr- If two finite sets are equal and two summands agree on every element, their sums are equal.
- Classical logic is invoked at the start so that graph coloring properties and set memberships can be decided, allowing them to be written as if-then-else indicator functions.
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_coeff_coeff {V : Type*} [Fintype V] (G : SimpleGraph V) (n k j : ℕ) : ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j = Fintype.card {c : G.Coloring (Fin n) // (Finset.univ.image c).card = k ∧ ∑ v : V, (c v : ℕ) = j} := by classical unfold simple_graph_t_chromatic_principal_specialization rw [Polynomial.finsetSum_coeff, Polynomial.finsetSum_coeff] simp only [Polynomial.coeff_monomial] rw [Fintype.card_subtype] rw [Finset.card_eq_sum_ones, Finset.sum_filter] refine Finset.sum_congr rfl (fun c _ => ?_) by_cases h1 : (Finset.univ.image c).card = k <;> by_cases h2 : ∑ v : V, (c v : ℕ) = j <;> simp [h1, h2, Polynomial.coeff_monomial]