Newton's identities for the hypergraph characteristic polynomial with Morozov–Shakirov traces
ProvedHararySachs.Hyper.newton_traceshypergraphsresultantsspectral-graph-theory
Let be a -uniform hypergraph on vertices with and edge set . Let be its characteristic polynomial, the resultant of . Write and for the codegree- coefficient.
Let be the -th Morozov–Shakirov trace of , given by the differential-operator formula of equation (1) in the source. Then for :
These are Newton's identities for in which the power sums of the eigenvalues have been replaced by the traces . Equivalently, they are the coefficientwise form of the Morozov–Shakirov formula
That formula is the deep, resultant-theoretic input to the Harary–Sachs theorem. A natural further decomposition is:
- splits over with roots (the eigenvalues).
- The -th power sum of the eigenvalues equals .
- Newton's identities and Vieta's formulas combine (1) and (2) into the displayed recursion.
Preamble
import Mathlib import Definitions.Def_HararySachs_Hyper_CharPoly import Definitions.Def_HararySachs_Hyper_Operators
Formal statement
namespace HararySachs.Hyper
theorem newton_traces (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)
(d : ℕ) (hd1 : 1 ≤ d) (hdt : d ≤ n * (k - 1) ^ (n - 1)) :
(d : ℚ) * codegCoeff (k := k) E res d =
-∑ j ∈ Finset.Icc 1 d, Tr (k := k) E j * codegCoeff (k := k) E res (d - j) := by sorry
end HararySachs.Hyper
Source
Morozov–Shakirov, Analogue of the identity Log Det = Trace Log for resultants, J. Geom. Phys. 61 (2011); Cooper–Dutle, Spectra of uniform hypergraphs, Linear Algebra Appl. 436 (2012); Clark–Cooper, arXiv:1812.00468v2, Section 2, equation (1) and the trace formula used in the proof of Theorem 14.