AFTD Auto-Formalizing Theoretical Domains

simple_graph_t_chromatic_ps_min_add_max_q_degree

theoremverified

For 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 ps_n(Z_G(x; t)) is nonzero, then (n-1)|V| = d + D.

Statement

theorem simple_graph_t_chromatic_ps_min_add_max_q_degree {V : Type*} [Fintype V] (G : SimpleGraph V) (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) :
    (n - 1) * Fintype.card V = d + D
Source
arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16(1), the step (n-1)|V| = d + D
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 2

The proof, explained

The theorem characterizes the q-degrees appearing with nonzero coefficient in the principal specialization as the vertex color sums ∑_{v ∈ V} c(v) of proper n-colorings c. Color reversal i ↦ n - 1 - i defines an involution on proper colorings such that the sum of the color sum of any coloring c and that of its reversal r(c) is identically (n - 1)|V|. Applying this identity to a coloring c0 achieving the minimal sum d shows that (n - 1)|V| - d ≤ D, while applying it to a coloring c1 achieving the maximal sum D shows that d ≤ (n - 1)|V| - D, which together force (n - 1)|V| = d + D.

  1. An exponent j of q appears with nonzero coefficient in the principal specialization if and only if there exists a proper n-coloring c of G with color sum ∑ v, c(v) = j.

    Using the coefficient formula for the principal specialization (`simple_graph_t_chromatic_ps_coeff_coeff`), the condition that some coefficient is nonzero is rewritten via `Fintype.card_eq_zero_iff` and `not_isEmpty_iff` to the nonemptiness of the set of colorings with image size k and color sum j. The forward direction discards the image size k, while the reverse direction takes k to be the cardinality of the image of c.

    lines 4–7

    uses Set.mem_setOf_eq, simple_graph_t_chromatic_ps_coeff_coeff, ne_eq, Fintype.card_eq_zero_iff, not_isEmpty_iff

      simp only [Set.mem_setOf_eq, simple_graph_t_chromatic_ps_coeff_coeff, ne_eq, Fintype.card_eq_zero_iff, not_isEmpty_iff]
      constructor
      · rintro ⟨k, ⟨c, -, hc⟩⟩; exact ⟨c, hc⟩
      · rintro ⟨c, hc⟩; exact ⟨_, ⟨c, rfl, hc⟩⟩
  2. There exist proper n-colorings c0 and c1 of G whose color sums are d and D, respectively.

    Because d is the least element and D is the greatest element of the set of non-vanishing q-exponents, both d and D belong to this set. Applying the forward direction of `simple_graph_t_chromatic_ps_min_add_max_q_degree_mem` produces proper colorings c0 with sum d and c1 with sum D.

    lines 13–15

    uses simple_graph_t_chromatic_ps_min_add_max_q_degree_mem

      classical
      obtain ⟨c0, hc0⟩ := (simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n d).1 hd.1
      obtain ⟨c1, hc1⟩ := (simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n D).1 hD.1
  3. Color reversal r(c)(v) = rev(c(v)) defines an operation sending any proper n-coloring of G to another proper n-coloring of G.

    Assigning each vertex v the reversed color Fin.rev(c(v)) via `SimpleGraph.Coloring.mk` produces a valid coloring because Fin.rev is injective (`Fin.rev_injective`), so adjacent vertices with distinct colors in c remain assigned distinct colors in r(c).

    lines 16–17

    uses SimpleGraph.Coloring.mk, Fin.rev, Fin.rev_injective

      let r : G.Coloring (Fin n) → G.Coloring (Fin n) := fun c =>
        SimpleGraph.Coloring.mk (fun v => Fin.rev (c v)) (fun h e => c.valid h (Fin.rev_injective e))
  4. For any proper n-coloring c of G, the sum of the color sum of r(c) and the color sum of c equals (n - 1)|V|.

    Combining the two vertex sums via `Finset.sum_add_distrib`, at each vertex v the sum of the reversed color and original color is (n - 1 - c(v)) + c(v) = n - 1 by `Fin.val_rev` and `Fin.isLt`. Summing this constant value n - 1 over all vertices in V gives (n - 1)|V| using `Finset.sum_const`, `Finset.card_univ`, and `smul_eq_mul`.

    lines 18–26

    uses Finset.sum_add_distrib, Fin.val_rev, Fin.isLt, Finset.sum_const, Finset.card_univ, smul_eq_mul

      have hW : ∀ c : G.Coloring (Fin n), ∑ v : V, ((r c) v : ℕ) + ∑ v : V, (c v : ℕ) = (n - 1) * Fintype.card V := by
        intro c
        rw [← Finset.sum_add_distrib]
        have : ∀ v, ((r c) v : ℕ) + (c v : ℕ) = n - 1 := by
          intro v
          show ((Fin.rev (c v) : Fin n) : ℕ) + (c v : ℕ) = n - 1
          rw [Fin.val_rev]; have := (c v).isLt; omega
        simp only [this, Finset.sum_const, Finset.card_univ, smul_eq_mul]
        ring
  5. The color sums of r(c0) and r(c1) satisfy ∑ v, r(c0)(v) ≤ D and d ≤ ∑ v, r(c1)(v), while summing each with d and D respectively gives (n - 1)|V|.

    Since r(c0) and r(c1) are proper colorings, their color sums belong to the set of non-vanishing q-exponents by `simple_graph_t_chromatic_ps_min_add_max_q_degree_mem`. Because D is greatest and d is least, ∑ v, r(c0)(v) ≤ D and d ≤ ∑ v, r(c1)(v). Furthermore, the coloring sum identity hW applied to c0 and c1 yields ∑ v, r(c0)(v) + d = (n - 1)|V| and ∑ v, r(c1)(v) + D = (n - 1)|V|.

    lines 27–30

    uses simple_graph_t_chromatic_ps_min_add_max_q_degree_mem

      have h1 := hD.2 ((simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n _).2 ⟨r c0, rfl⟩)
      have h2 := hd.2 ((simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n _).2 ⟨r c1, rfl⟩)
      have e0 := hW c0
      have e1 := hW c1
  6. (n - 1)|V| = d + D. automation

    Linear arithmetic over ℕ (`omega`) combines ∑ v, r(c0)(v) + d = (n - 1)|V| with ∑ v, r(c0)(v) ≤ D to give (n - 1)|V| ≤ d + D, and combines ∑ v, r(c1)(v) + D = (n - 1)|V| with d ≤ ∑ v, r(c1)(v) to give d + D ≤ (n - 1)|V|, forcing equality.

    line 31

      omega
Set.mem_setOf_eq
An element x belongs to the set {y | p y} if and only if p x holds.
simple_graph_t_chromatic_ps_coeff_coeff
The coefficient of t^k q^j in the principal specialization ps_n(Z_G) is the number of proper n-colorings of G whose image has cardinality k and whose color sum is j.
ne_eq
The inequality a ≠ b is defined as the negation of a = b.
Fintype.card_eq_zero_iff
The cardinality of a finite type is zero if and only if the type is empty.
not_isEmpty_iff
A type is not empty if and only if it is nonempty.
simple_graph_t_chromatic_ps_min_add_max_q_degree_mem
An exponent j appears with a nonzero coefficient in the principal specialization if and only if there exists a proper n-coloring of G with color sum j.
SimpleGraph.Coloring.mk
Constructs a proper coloring of a graph from a vertex coloring function and a proof that adjacent vertices receive different colors.
Fin.rev
The reversal permutation on Fin n, mapping each element i to n - 1 - i.
Fin.rev_injective
The reversal function on Fin n is injective.
Finset.sum_add_distrib
The sum of a pointwise sum of two functions over a finite set equals the sum of their individual sums.
Fin.val_rev
The numerical value of the reversed element rev(i) in Fin n is n - (i + 1).
Fin.isLt
The numerical value of an element of Fin n is strictly less than n.
Finset.sum_const
The sum of a constant value over a finite set equals the cardinality of the set times that value.
Finset.card_univ
The cardinality of the universal finset of a finite type is the cardinality of the type.
smul_eq_mul
Scalar multiplication of natural numbers coincides with ordinary multiplication.

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

theorem simple_graph_t_chromatic_ps_min_add_max_q_degree_mem {V : Type*} [Fintype V] (G : SimpleGraph V) (n j : ℕ) :    j ∈ {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} ↔      ∃ c : G.Coloring (Fin n), ∑ v : V, (c v : ℕ) = j := by  simp only [Set.mem_setOf_eq, simple_graph_t_chromatic_ps_coeff_coeff, ne_eq, Fintype.card_eq_zero_iff, not_isEmpty_iff]  constructor  · rintro ⟨k, ⟨c, -, hc⟩⟩; exact ⟨c, hc⟩  · rintro ⟨c, hc⟩; exact ⟨_, ⟨c, rfl, hc⟩⟩theorem simple_graph_t_chromatic_ps_min_add_max_q_degree {V : Type*} [Fintype V] (G : SimpleGraph V) (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) :    (n - 1) * Fintype.card V = d + D := by  classical  obtain ⟨c0, hc0⟩ := (simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n d).1 hd.1  obtain ⟨c1, hc1⟩ := (simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n D).1 hD.1  let r : G.Coloring (Fin n) → G.Coloring (Fin n) := fun c =>    SimpleGraph.Coloring.mk (fun v => Fin.rev (c v)) (fun h e => c.valid h (Fin.rev_injective e))  have hW : ∀ c : G.Coloring (Fin n), ∑ v : V, ((r c) v : ℕ) + ∑ v : V, (c v : ℕ) = (n - 1) * Fintype.card V := by    intro c    rw [← Finset.sum_add_distrib]    have : ∀ v, ((r c) v : ℕ) + (c v : ℕ) = n - 1 := by      intro v      show ((Fin.rev (c v) : Fin n) : ℕ) + (c v : ℕ) = n - 1      rw [Fin.val_rev]; have := (c v).isLt; omega    simp only [this, Finset.sum_const, Finset.card_univ, smul_eq_mul]    ring  have h1 := hD.2 ((simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n _).2 ⟨r c0, rfl⟩)  have h2 := hd.2 ((simple_graph_t_chromatic_ps_min_add_max_q_degree_mem G n _).2 ⟨r c1, rfl⟩)  have e0 := hW c0  have e1 := hW c1  omega
See it in the graphDiscuss this resultChallenge it