simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite
Let n ≥ 2 and let G be a connected finite simple graph with at least 2 vertices that has a proper coloring with n colors, and let b : V → Fin 2 be a proper 2-coloring of G (so G is bipartite). Let c1 and c2 be the smaller and the larger of the sizes of the two parts {v | b v = 0} and {v | b v = 1}. Then the coefficient of t^2 in ps_n(Z_G(x; t)) equals the sum over ordered pairs (j1, j2) of distinct elements of {0, ..., n-1} of q^(c1 j1 + c2 j2).
Statement
theorem simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 2 ≤ n) (hV : 2 ≤ Fintype.card V) (hcol : G.Colorable n) (hconn : G.Connected) (b : G.Coloring (Fin 2)) : (simple_graph_t_chromatic_principal_specialization G n).coeff 2 = ∑ p ∈ Finset.univ.filter (fun p : Fin n × Fin n => p.1 ≠ p.2), Polynomial.X ^ (min (Finset.univ.filter (fun v => b v = 0)).card (Finset.univ.filter (fun v => b v = 1)).card * (p.1 : ℕ) + max (Finset.univ.filter (fun v => b v = 0)).card (Finset.univ.filter (fun v => b v = 1)).card * (p.2 : ℕ))
- Formalizes
- arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16(3); the bipartition is given as a proper 2-coloring b, whose parts are the unique bipartition of the connected graph
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_t_two_of_edgeLet G be a connected finite simple graph with a proper 2-coloring b : V → Fin 2 and an edge u0 w0 with b u0 = 0, b w0 = 1. Let s0, s1 be…
- fin_pair_ne_sum_pow_swapFor natural numbers n, a, b, the sum over ordered pairs (j1, j2) of distinct elements of Fin n of X^(a j1 + b j2) in ℕ[X] equals the sum…
Read back from the Lean
Let $V$ be a finite type, and let $G$ be a simple graph on $V$. Let $n$ be a natural number such that $2 \le n$. Assume that $V$ has at least 2 vertices, that $G$ is $n$-colorable, that $G$ is connected, and let $b$ be a proper 2-coloring of $G$ with colors in $\operatorname{Fin} 2$.
Then the coefficient at degree 2 of the principal specialization of the $t$-chromatic polynomial of $G$ with $n$ colors, simple_graph_t_chromatic_principal_specialization G n, is equal to the sum over all pairs $(p_1, p_2) \in \operatorname{Fin} n \times \operatorname{Fin} n$ with $p_1 \ne p_2$ of:
$$X^{\min(|b^{-1}(0)|, |b^{-1}(1)|) \cdot p_1 + \max(|b^{-1}(0)|, |b^{-1}(1)|) \cdot p_2}$$
as a polynomial in $\mathbb{N}[X]$ (where $p_1, p_2$ are coerced to natural numbers, and $b^{-1}(0), b^{-1}(1)$ denote the sets of vertices mapped by $b$ to $0$ and $1$, respectively).
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
Because G is connected and has at least two vertices, it contains at least one edge, whose endpoints must receive distinct colors 0 and 1 under the proper 2-coloring b. This allows applying simple_graph_t_chromatic_ps_coeff_t_two_of_edge, which expresses the t²-coefficient as a sum of powers X^(|b⁻¹(0)| p₁ + |b⁻¹(1)| p₂) over distinct pairs (p₁, p₂). Finally, a case analysis on the relative sizes of the two color classes simplifies the minimum and maximum, using the symmetry of the sum under swapping distinct indices (fin_pair_ne_sum_pow_swap) when |b⁻¹(1)| ≤ |b⁻¹(0)|.
An element of Fin 2 is nonzero if and only if it equals 1. automation
This auxiliary lemma proves that for any a ∈ Fin 2, ¬(a = 0) ↔ a = 1 by case analysis on the two elements of Fin 2 and direct computation.
theorem simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two (a : Fin 2) : ¬ a = 0 ↔ a = 1 := by fin_cases a <;> decide
The graph G contains at least one edge.
Since |V| ≥ 2, the vertex set has more than one element (by linear arithmetic via omega), so there exist distinct vertices x ≠ y by Fintype.exists_pair_of_one_lt_card. Because G is connected, there is a walk p from x to y. Since x ≠ y, this walk cannot be empty; its first step gives an edge between x and an adjacent vertex, yielding adjacent vertices u, w.
uses
Fintype.exists_pair_of_one_lt_cardclassical obtain ⟨x, y, hxy⟩ := Fintype.exists_pair_of_one_lt_card (by omega : 1 < Fintype.card V) obtain ⟨p⟩ := hconn.preconnected x y have : ∃ u w, G.Adj u w := by cases p with | nil => exact absurd rfl hxy | cons h _ => exact ⟨_, _, h⟩ obtain ⟨u, w, huw⟩ := this
There exists an edge in G whose endpoints are colored 0 and 1 by the 2-coloring b.
Because b is a proper 2-coloring and u is adjacent to w, the colors b(u) and b(w) in Fin 2 must differ. A case distinction on whether b(u) = 0 shows that either b(u) = 0 and b(w) = 1 (using simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two), so the edge (u, w) works, or b(u) ≠ 0 (hence b(u) = 1) and b(w) = 0, so the reversed edge (w, u) works by symmetry of adjacency.
uses
simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_twohave hbuw := b.valid huw have key : ∃ u0 w0, b u0 = 0 ∧ b w0 = 1 ∧ G.Adj u0 w0 := by by_cases hu : b u = 0 · exact ⟨u, w, hu, (simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two _).1 (fun h => hbuw (hu.trans h.symm)), huw⟩ · exact ⟨w, u, by rw [simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two] at hu; by_contra h; rw [simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two] at h; exact hbuw (hu.trans h.symm), (simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two _).1 hu, huw.symm⟩ obtain ⟨u0, w0, hb0, hb1, hadj⟩ := key
The coefficient of t² equals the sum over distinct pairs (p₁, p₂) of X^(|b⁻¹(0)| p₁ + |b⁻¹(1)| p₂).
We rewrite the goal using simple_graph_t_chromatic_ps_coeff_t_two_of_edge, which applies to any connected graph with a 2-coloring and an edge connecting vertices of colors 0 and 1.
uses
simple_graph_t_chromatic_ps_coeff_t_two_of_edgerw [simple_graph_t_chromatic_ps_coeff_t_two_of_edge G n hconn b u0 w0 hb0 hb1 hadj]The sum matches the required formula where the exponents are ordered by the minimum and maximum of the color class sizes.
By totality of the ordering on ℕ (le_total), either |b⁻¹(0)| ≤ |b⁻¹(1)| or |b⁻¹(1)| ≤ |b⁻¹(0)|. In the first case, min_eq_left and max_eq_right rewrite the minimum and maximum directly into |b⁻¹(0)| and |b⁻¹(1)|. In the second case, min_eq_right and max_eq_left simplify the minimum and maximum, and fin_pair_ne_sum_pow_swap swaps the dummy summation indices p₁ and p₂ to match the LHS.
uses
le_total,min_eq_left,max_eq_right,min_eq_right,max_eq_left,fin_pair_ne_sum_pow_swaprcases le_total (Finset.univ.filter (fun v => b v = 0)).card (Finset.univ.filter (fun v => b v = 1)).card with h | h · rw [min_eq_left h, max_eq_right h] · rw [min_eq_right h, max_eq_left h, fin_pair_ne_sum_pow_swap]
simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two- For any element a in Fin 2, a is nonzero if and only if a equals 1.
Fintype.exists_pair_of_one_lt_card- A finite type with cardinality strictly greater than 1 contains at least two distinct elements.
simple_graph_t_chromatic_ps_coeff_t_two_of_edge- For a connected graph with a 2-coloring and an edge connecting a vertex colored 0 to a vertex colored 1, the t²-coefficient of its chromatic principal specialization equals the sum over distinct pairs (p₁, p₂) of X^(|b⁻¹(0)| p₁ + |b⁻¹(1)| p₂).
le_total- For any two elements a, b in a linear order, either a ≤ b or b ≤ a.
min_eq_left- If a ≤ b in a linear order, then min(a, b) = a.
max_eq_right- If a ≤ b in a linear order, then max(a, b) = b.
min_eq_right- If b ≤ a in a linear order, then min(a, b) = b.
max_eq_left- If b ≤ a in a linear order, then max(a, b) = a.
fin_pair_ne_sum_pow_swap- The sum of X^(a p₁ + b p₂) over all pairs of distinct elements (p₁, p₂) in Fin n × Fin n equals the sum of X^(b p₁ + a p₂) over the same set.
- The indeterminate Polynomial.X in Lean corresponds to the variable q in the mathematical formulation.
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_coeff_t_two_connected_bipartite_fin_two (a : Fin 2) : ¬ a = 0 ↔ a = 1 := by fin_cases a <;> decidetheorem simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 2 ≤ n) (hV : 2 ≤ Fintype.card V) (hcol : G.Colorable n) (hconn : G.Connected) (b : G.Coloring (Fin 2)) : (simple_graph_t_chromatic_principal_specialization G n).coeff 2 = ∑ p ∈ Finset.univ.filter (fun p : Fin n × Fin n => p.1 ≠ p.2), Polynomial.X ^ (min (Finset.univ.filter (fun v => b v = 0)).card (Finset.univ.filter (fun v => b v = 1)).card * (p.1 : ℕ) + max (Finset.univ.filter (fun v => b v = 0)).card (Finset.univ.filter (fun v => b v = 1)).card * (p.2 : ℕ)) := by classical obtain ⟨x, y, hxy⟩ := Fintype.exists_pair_of_one_lt_card (by omega : 1 < Fintype.card V) obtain ⟨p⟩ := hconn.preconnected x y have : ∃ u w, G.Adj u w := by cases p with | nil => exact absurd rfl hxy | cons h _ => exact ⟨_, _, h⟩ obtain ⟨u, w, huw⟩ := this have hbuw := b.valid huw have key : ∃ u0 w0, b u0 = 0 ∧ b w0 = 1 ∧ G.Adj u0 w0 := by by_cases hu : b u = 0 · exact ⟨u, w, hu, (simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two _).1 (fun h => hbuw (hu.trans h.symm)), huw⟩ · exact ⟨w, u, by rw [simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two] at hu; by_contra h; rw [simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two] at h; exact hbuw (hu.trans h.symm), (simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two _).1 hu, huw.symm⟩ obtain ⟨u0, w0, hb0, hb1, hadj⟩ := key rw [simple_graph_t_chromatic_ps_coeff_t_two_of_edge G n hconn b u0 w0 hb0 hb1 hadj] rcases le_total (Finset.univ.filter (fun v => b v = 0)).card (Finset.univ.filter (fun v => b v = 1)).card with h | h · rw [min_eq_left h, max_eq_right h] · rw [min_eq_right h, max_eq_left h, fin_pair_ne_sum_pow_swap]