AFTD Auto-Formalizing Theoretical Domains

simple_graph_t_chromatic_ps_determines_chromatic_ps

theoremverifiedformalization

Let 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 specialization of the t-chromatic symmetric function of G equals that of H, then the n-th principal specialization of the chromatic symmetric function of G equals that of H.

Statement

theorem simple_graph_t_chromatic_ps_determines_chromatic_ps
    {V W : Type*} [Fintype V] [Fintype W]
    (G : SimpleGraph V) (H : SimpleGraph W) (n : ℕ) (_hn : 0 < n)
    (h : simple_graph_t_chromatic_principal_specialization G n =
         simple_graph_t_chromatic_principal_specialization H n) :
    simple_graph_chromatic_principal_specialization G n =
      simple_graph_chromatic_principal_specialization H n
Formalizes
arXiv:2610.31785, Proposition 3.9
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

Read back from the Lean

Let $V$ and $W$ be finite types, let $G$ be a simple graph on $V$, let $H$ be a simple graph on $W$, and let $n$ be a positive natural number ($0 < n$). If the $t$-chromatic principal specialization of $G$ at $n$ equals the $t$-chromatic principal specialization of $H$ at $n$, then the chromatic principal specialization of $G$ at $n$ equals the chromatic principal specialization of $H$ at $n$.

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 chromatic principal specialization of a graph is obtained directly by evaluating its $t$-chromatic principal specialization at $t = 1$. Since the $n$-th $t$-chromatic principal specializations of $G$ and $H$ are assumed to be identical, evaluating both sides at $1$ shows that their $n$-th chromatic principal specializations are equal as well.

  1. The $n$-th principal specialization of the chromatic symmetric function of $G$ equals that of $H$.

    By `simple_graph_t_chromatic_ps_eval_one`, evaluating the $n$-th principal specialization of the $t$-chromatic symmetric function at $1$ recovers the chromatic principal specialization. Rewriting both the left-hand side (for $G$) and the right-hand side (for $H$) in this form, the goal reduces to showing that evaluating the $t$-chromatic principal specialization of $G$ at $1$ equals evaluating that of $H$ at $1$. This follows immediately by rewriting with the assumption $h$ that the two $t$-chromatic principal specializations are equal.

    lines 9–10

    uses simple_graph_t_chromatic_ps_eval_one

      rw [← simple_graph_t_chromatic_ps_eval_one G n,
        ← simple_graph_t_chromatic_ps_eval_one H n, h]
simple_graph_t_chromatic_ps_eval_one
Evaluating the $n$-th principal specialization of the $t$-chromatic symmetric function of a finite graph at 1 yields the $n$-th principal specialization of its chromatic symmetric function.

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

/-- Proposition 3.9: Equality of the n-th principal specializations of the t-chromatic symmetric function implies equality of the principal specializations of the chromatic symmetric function. -/theorem simple_graph_t_chromatic_ps_determines_chromatic_ps    {V W : Type*} [Fintype V] [Fintype W]    (G : SimpleGraph V) (H : SimpleGraph W) (n : ℕ) (_hn : 0 < n)    (h : simple_graph_t_chromatic_principal_specialization G n =         simple_graph_t_chromatic_principal_specialization H n) :    simple_graph_chromatic_principal_specialization G n =      simple_graph_chromatic_principal_specialization H n := by  rw [← simple_graph_t_chromatic_ps_eval_one G n,    ← simple_graph_t_chromatic_ps_eval_one H n, h]
See it in the graphDiscuss this resultChallenge it