third_principal_specialization
The third principal specialization of the t-chromatic symmetric function of a graph G is the bivariate polynomial in Z[q, t] given by the sum over all proper 3-colorings c of G of q raised to the sum of vertex colors times t raised to the number of distinct colors used.
Statement
noncomputable def third_principal_specialization {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : MvPolynomial (Fin 2) ℤ
- Defined in
- arXiv:2610.31785 Definition 3.8 and Equation (3.1)
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Used by 4
- caterpillar_card_eq_of_third_principal_specialization_eqIf two finite caterpillars have equal third principal specializations, their vertex sets have equal cardinalities.
- third_principal_specialization_congrIf two finite graphs are isomorphic, their third principal specializations are equal as bivariate polynomials.
- third_principal_specialization_eval_oneEvaluating the third principal specialization of a graph G at (1, 1) via MvPolynomial.eval (fun _ => 1) equals the number of proper…
- third_principal_specialization_card_eqThe third principal specialization of any finite tree on at least one vertex uniquely determines its number of vertices.
Read back from the Lean
Given a finite type V with decidable equality and a simple graph G on V with decidable adjacency, third_principal_specialization G is defined as the element of MvPolynomial (Fin 2) ℤ (the two-variable polynomial ring over ℤ with variables indexed by 0 and 1) given by:
∑ c, (X 0) ^ (∑ v : V, (c v).val) * (X 1) ^ |c(V)|
where the outer sum runs over all proper 3-colorings c : G.Coloring (Fin 3) (i.e., functions c : V → Fin 3 such that G.Adj u v → c u ≠ c v), (c v).val ∈ {0, 1, 2} is the numerical value of the color assigned to vertex v, and |c(V)| ((Finset.univ.image c).card) is the number of distinct colors assigned by c.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The third principal specialization of the t-chromatic symmetric function of a graph as a polynomial in Z[q, t]. -/ noncomputable def third_principal_specialization {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : MvPolynomial (Fin 2) ℤ := ∑ c : G.Coloring (Fin 3), (MvPolynomial.X 0) ^ (∑ v : V, (c v).val) * (MvPolynomial.X 1) ^ (Finset.univ.image c).card