simple_graph_t_chromatic_ps_q_coeff_symm
Let 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 and maximum degrees of q appearing in ps_n(Z_G(x; t)). Then for every j with d ≤ j ≤ D, the coefficient of q^j in ps_n(Z_G(x; t)) (a polynomial in t) equals the coefficient of q^(d+D-j); that is, for every k the coefficients of t^k q^j and t^k q^(d+D-j) agree.
Statement
theorem simple_graph_t_chromatic_ps_q_coeff_symm {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 2 ≤ n) (hV : 2 ≤ Fintype.card V) (hcol : G.Colorable n) (d D : ℕ) (hd : IsLeast {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} d) (hD : IsGreatest {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} D) : ∀ j, d ≤ j → j ≤ D → ∀ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j = ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff (d + D - j)
- Formalizes
- arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16(2)
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_t_chromatic_ps_coeff_coeffFor 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_ps_coloring_count_revFor a finite simple graph G, natural numbers n, k and j ≤ (n-1)|V|, the number of proper colorings c : V → Fin n with exactly k colors and…
- 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…
Read back from the Lean
Let $V$ be a finite type with at least 2 elements, and let $G$ be a simple graph on $V$. Let $n \ge 2$ be a natural number, and assume $G$ is $n$-colorable. Let $d, D \in \mathbb{N}$.
Assume that $d$ is the least element of the set of natural numbers $j$ such that there exists $k \in \mathbb{N}$ for which the $k$-th outer coefficient, evaluated at the $j$-th inner coefficient, of simple_graph_t_chromatic_principal_specialization G n is nonzero.
Assume that $D$ is the greatest element of that same set.
Then, for all natural numbers $j$ satisfying $d \le j \le D$, and for all $k \in \mathbb{N}$, the $j$-th inner coefficient of the $k$-th outer coefficient of simple_graph_t_chromatic_principal_specialization G n equals its $(d + D - j)$-th inner coefficient.
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 coefficient of t^k q^j in the principal specialization ps_n(Z_G(x; t)) counts the number of proper n-colorings of G using k colors whose vertex colors sum to j. Inverting colors via c(v) ↦ (n - 1) - c(v) yields a bijection between colorings with sum j and those with sum (n - 1)|V| - j. Since the minimum and maximum q-degrees satisfy d + D = (n - 1)|V|, this reflection (n - 1)|V| - j equals d + D - j, proving the coefficient symmetry.
Fix an exponent j with j ≤ D and an exponent k.
We introduce j, the upper bound j ≤ D (the lower bound d ≤ j is unused), and the exponent k of t.
intro j _ hjD kThe sum of the minimum and maximum q-degrees satisfies d + D = (n - 1)|V|.
By simple_graph_t_chromatic_ps_min_add_max_q_degree, the sum of the least q-degree d and greatest q-degree D appearing with non-zero coefficient in the principal specialization is equal to (n - 1)|V|.
uses
simple_graph_t_chromatic_ps_min_add_max_q_degreehave h := simple_graph_t_chromatic_ps_min_add_max_q_degree G n d D hd hDThe coefficient of t^k q^j equals the coefficient of t^k q^(d + D - j).
Rewriting both sides with simple_graph_t_chromatic_ps_coeff_coeff expresses each coefficient as the number of proper n-colorings using k colors whose vertex colors sum to j and d + D - j, respectively. Then simple_graph_t_chromatic_ps_coloring_count_rev equates the count for sum j with the count for sum (n - 1)|V| - j (where the side condition j ≤ (n - 1)|V| is discharged by linear arithmetic via `omega` since j ≤ D ≤ d + D = (n - 1)|V|). Finally, rewriting with h replaces (n - 1)|V| with d + D, completing the proof.
uses
simple_graph_t_chromatic_ps_coeff_coeff,simple_graph_t_chromatic_ps_coloring_count_revrw [simple_graph_t_chromatic_ps_coeff_coeff, simple_graph_t_chromatic_ps_coeff_coeff, simple_graph_t_chromatic_ps_coloring_count_rev G n k j (by omega), h]
simple_graph_t_chromatic_ps_min_add_max_q_degree- For a graph G and n colors, the sum of the minimum degree d and maximum degree D of q with non-zero coefficient in the principal specialization is (n - 1)|V|.
simple_graph_t_chromatic_ps_coeff_coeff- The coefficient of t^k q^j in the principal specialization is the number of proper n-colorings of G using exactly k colors whose vertex color values sum to j.
simple_graph_t_chromatic_ps_coloring_count_rev- For j ≤ (n - 1)|V|, the number of proper n-colorings of G using k colors with vertex color sum j equals the number of such colorings with vertex color sum (n - 1)|V| - j.
- The hypothesis d ≤ j is formally unused in the proof (as indicated by the underscore in `intro j _ hjD k`), since j ≤ D together with d ≥ 0 implies j ≤ d + D = (n - 1)|V|.
- The side condition j ≤ (n - 1)|V| required by simple_graph_t_chromatic_ps_coloring_count_rev is discharged automatically by `omega` using linear integer arithmetic.
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_q_coeff_symm {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 2 ≤ n) (hV : 2 ≤ Fintype.card V) (hcol : G.Colorable n) (d D : ℕ) (hd : IsLeast {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} d) (hD : IsGreatest {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} D) : ∀ j, d ≤ j → j ≤ D → ∀ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j = ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff (d + D - j) := by intro j _ hjD k have h := simple_graph_t_chromatic_ps_min_add_max_q_degree G n d D hd hD rw [simple_graph_t_chromatic_ps_coeff_coeff, simple_graph_t_chromatic_ps_coeff_coeff, simple_graph_t_chromatic_ps_coloring_count_rev G n k j (by omega), h]