third_principal_specialization_congr
If two finite graphs are isomorphic, their third principal specializations are equal as bivariate polynomials.
Statement
theorem third_principal_specialization_congr {V W : Type*} [Fintype V] [DecidableEq V] [Fintype W] [DecidableEq W] (G : SimpleGraph V) (H : SimpleGraph W) [DecidableRel G.Adj] [DecidableRel H.Adj] (e : G ≃g H) : third_principal_specialization G = third_principal_specialization H
- Source
- arXiv:2610.31785 Proposition 3.3
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- third_principal_specializationThe third principal specialization of the t-chromatic symmetric function of a graph G is the bivariate polynomial in Z[q, t] given by the…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
Let $V$ and $W$ be finite types with decidable equality, and let $G$ and $H$ be simple graphs on $V$ and $W$, respectively, each with decidable adjacency relations. If $e : G \simeq_g H$ is a graph isomorphism, then third_principal_specialization G = third_principal_specialization H.
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 third principal specialization of a graph is a bivariate polynomial defined as a sum over all 3-colorings c of the term X₀^(∑ v, c(v)) * X₁^(|im(c)|). Given a graph isomorphism e : G ≃g H, pulling back colorings along e defines an equivalence between the 3-colorings of H and G. Reindexing the sum for G by this equivalence reduces the equality to showing that each summand is invariant under precomposition with e. The invariance of the X₀-exponent follows by reindexing the sum of color values via the vertex bijection e, while the invariance of the X₁-exponent follows because the bijection e maps the universal vertex set of G onto that of H, preserving the image of the coloring.
An isomorphism of simple graphs e : G ≃g H induces an equivalence between their coloring types H.Coloring α ≃ G.Coloring α.
Pulling back along the graph homomorphism e : G → H sends any valid coloring of H to a valid coloring of G. The inverse mapping pulls back along e⁻¹ : H → G. These operations are mutually inverse because precomposing with e and then e⁻¹ (or vice versa) yields the identity coloring by extensionality and simplification.
def third_principal_specialization_congr_coloring_equiv {V W α : Type*} (G : SimpleGraph V) (H : SimpleGraph W) (e : G ≃g H) : H.Coloring α ≃ G.Coloring α where toFun c := c.comp e.toHom invFun c := c.comp e.symm.toHom left_inv c := by ext; simp right_inv c := by ext; simp
To show that the third principal specializations of G and H are equal, it suffices to prove that for every 3-coloring c of H, the polynomial term for c ∘ e on G equals the polynomial term for c on H.
Unfolding the definition of third_principal_specialization expresses each side as a sum over colorings. By Equiv.sum_comp, reindexing the sum over colorings of G via the equivalence third_principal_specialization_congr_coloring_equiv G H e converts it into a sum over colorings of H. Then Fintype.sum_congr reduces the equality of the two sums to checking that their summands agree for each coloring c of H.
uses
third_principal_specialization_congr_coloring_equiv,Equiv.sum_comp,Fintype.sum_congrtheorem third_principal_specialization_congr {V W : Type*} [Fintype V] [DecidableEq V] [Fintype W] [DecidableEq W] (G : SimpleGraph V) (H : SimpleGraph W) [DecidableRel G.Adj] [DecidableRel H.Adj] (e : G ≃g H) : third_principal_specialization G = third_principal_specialization H := by unfold third_principal_specialization rw [← Equiv.sum_comp (third_principal_specialization_congr_coloring_equiv G H e)] apply Fintype.sum_congr intro c
The sum of the vertex color values on G for c ∘ e equals the sum of the vertex color values on H for c.
The vertex color value function v ↦ (c(e(v))).val on G is the composition of the vertex bijection e : V ≃ W with the color value function w ↦ (c(w)).val on H. By Equiv.sum_comp, reindexing the sum over V by the equivalence e preserves the sum of the color values.
uses
Equiv.sum_comphave h1 : ∑ v : V, ((c.comp e.toHom) v).val = ∑ w : W, (c w).val := by have h : (fun v => ((c.comp e.toHom) v).val) = (fun w => (c w).val) ∘ e.toEquiv := rfl rw [h] exact Equiv.sum_comp e.toEquiv (fun w => (c w).val)
The number of colors used by c ∘ e on G equals the number of colors used by c on H.
The coloring c ∘ e is the composite of the vertex equivalence e : V ≃ W and c : W → Fin 3. By Finset.image_image, the image of the universal finset of V under c ∘ e is the image under c of the image of V under e. Since e is an equivalence, the image of V under e is the universal finset of W by Finset.image_univ_equiv. Therefore, the sets of colors used by both colorings are identical, so their cardinalities match.
uses
Finset.image_image,Finset.image_univ_equivhave h2 : (Finset.univ.image (c.comp e.toHom)).card = (Finset.univ.image c).card := by have h : (c.comp e.toHom : V → Fin 3) = c ∘ e.toEquiv := rfl rw [h, ← Finset.image_image, Finset.image_univ_equiv]
The polynomial summands for c ∘ e and c are equal, completing the proof.
The summand for c ∘ e is X₀^(∑ v, (c(e(v))).val) * X₁^(|im(c ∘ e)|) and the summand for c is X₀^(∑ w, (c(w)).val) * X₁^(|im(c)|). Substituting the previously established equalities h1 (for the exponent of X₀) and h2 (for the exponent of X₁) shows that the two summands are identical.
show (MvPolynomial.X 0 ^ ∑ v, ((c.comp e.toHom) v).val) * MvPolynomial.X 1 ^ (Finset.image (c.comp e.toHom) Finset.univ).card = (MvPolynomial.X 0 ^ ∑ w, (c w).val) * MvPolynomial.X 1 ^ (Finset.image c Finset.univ).card rw [h1, h2]
third_principal_specialization_congr_coloring_equiv- A graph isomorphism between two graphs induces an equivalence between their coloring types (by precomposing with the isomorphism).
Equiv.sum_comp- Summing a function over a finite type is invariant under reindexing the domain by an equivalence: ∑ i, g (e i) = ∑ i, g i.
Fintype.sum_congr- Two sums over a finite type are equal if their summands agree at every element.
Finset.image_image- The image under g of the image of a finite set under f equals the image under the composition g ∘ f.
Finset.image_univ_equiv- The image of the universal finset under an equivalence between finite types is the universal finset of the codomain.
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.
def third_principal_specialization_congr_coloring_equiv {V W α : Type*} (G : SimpleGraph V) (H : SimpleGraph W) (e : G ≃g H) : H.Coloring α ≃ G.Coloring α where toFun c := c.comp e.toHom invFun c := c.comp e.symm.toHom left_inv c := by ext; simp right_inv c := by ext; simp/-- Isomorphic graphs have equal third principal specializations. -/theorem third_principal_specialization_congr {V W : Type*} [Fintype V] [DecidableEq V] [Fintype W] [DecidableEq W] (G : SimpleGraph V) (H : SimpleGraph W) [DecidableRel G.Adj] [DecidableRel H.Adj] (e : G ≃g H) : third_principal_specialization G = third_principal_specialization H := by unfold third_principal_specialization rw [← Equiv.sum_comp (third_principal_specialization_congr_coloring_equiv G H e)] apply Fintype.sum_congr intro c have h1 : ∑ v : V, ((c.comp e.toHom) v).val = ∑ w : W, (c w).val := by have h : (fun v => ((c.comp e.toHom) v).val) = (fun w => (c w).val) ∘ e.toEquiv := rfl rw [h] exact Equiv.sum_comp e.toEquiv (fun w => (c w).val) have h2 : (Finset.univ.image (c.comp e.toHom)).card = (Finset.univ.image c).card := by have h : (c.comp e.toHom : V → Fin 3) = c ∘ e.toEquiv := rfl rw [h, ← Finset.image_image, Finset.image_univ_equiv] show (MvPolynomial.X 0 ^ ∑ v, ((c.comp e.toHom) v).val) * MvPolynomial.X 1 ^ (Finset.image (c.comp e.toHom) Finset.univ).card = (MvPolynomial.X 0 ^ ∑ w, (c w).val) * MvPolynomial.X 1 ^ (Finset.image c Finset.univ).card rw [h1, h2]