Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The characteristic polynomial of a kkk-graph is monic of degree n(k−1)n−1n(k-1)^{n-1}n(k−1)n−1 (leading coefficient)

Proved
HararySachs.Hyper.charPoly_coeff_top

by milia · Nov 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

hypergraphsresultantsspectral-graph-theory

Let HHH be a kkk-uniform hypergraph on n≥1n \ge 1n≥1 vertices with k≥2k \ge 2k≥2, with edge set EEE, and let A\mathcal{A}A be its normalized adjacency hypermatrix. Let Res⁡\operatorname{Res}Res be the multivariate resultant of nnn homogeneous forms of degree k−1k-1k−1 in nnn variables. It is characterised by three properties:

  • it vanishes exactly when the forms have a common nontrivial zero over C\mathbb{C}C;
  • it is normalized to 111 on (x1k−1,…,xnk−1)(x_1^{k-1}, \dots, x_n^{k-1})(x1k−1​,…,xnk−1​);
  • it is irreducible.

The characteristic polynomial is

φH(λ)=Res⁡(λxik−1−(Axk−1)i)i=1n.\varphi_H(\lambda) = \operatorname{Res}\big(\lambda x_i^{k-1} - (\mathcal{A}x^{k-1})_i\big)_{i=1}^n.φH​(λ)=Res(λxik−1​−(Axk−1)i​)i=1n​.

Its coefficient of λN\lambda^{N}λN, where N=n(k−1)n−1N = n(k-1)^{n-1}N=n(k−1)n−1, equals 111.

Together with deg⁡φH=N\deg \varphi_H = NdegφH​=N, this is the statement that φH\varphi_HφH​ is monic of degree n(k−1)n−1n(k-1)^{n-1}n(k−1)n−1. It follows from the homogeneity of the resultant (degree (k−1)n−1(k-1)^{n-1}(k−1)n−1 in the coefficients of each form) and its normalization, since λ\lambdaλ enters only through the diagonal coefficients. (Edges have at least two vertices, so A\mathcal{A}A has no diagonal entries.) This fixes the constant term c0=1c_0 = 1c0​=1 in the Newton recursion for the codegree coefficients.

Preamble
import Mathlib
import Definitions.Def_HararySachs_Hyper_CharPoly
Formal statement
namespace HararySachs.Hyper

theorem charPoly_coeff_top (n k : ℕ) (hk : 2 ≤ k) (hn : 1 ≤ n)
    (E : Finset (Finset (Fin n))) (hE : ∀ e ∈ E, e.card = k)
    (res : MvPolynomial (ResVar n (fun _ => k - 1)) ℤ)
    (hres : IsResultant n (fun _ => k - 1) res) :
    (charPoly (k := k) E res).coeff (n * (k - 1) ^ (n - 1)) = 1 := by sorry

end HararySachs.Hyper
Source
Cooper–Dutle, Spectra of uniform hypergraphs, Linear Algebra Appl. 436 (2012), Section 2 (degree n(k−1)n−1n(k-1)^{n-1}n(k−1)n−1 of the characteristic polynomial); Clark–Cooper, arXiv:1812.00468v2, Section 2.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me