The Negami Polynomial and Broken-Circuit Stanley--Reisner Rings

Source abstract

We establish a direct connection between Seiya Negami's three-variable graph polynomial $f(G;t,x,y)$ and the Stanley-Reisner ring of the broken-circuit complex of the graphic matroid. For a connected loopless graph $G$, the chromatic specialization $f(G;q,-1,1)=P_G(q)$ together with Whitney's broken-circuit theorem yields \[ h_{\BC(G)}(z)=(-z)^r\left[\frac{f(G;q,-1,1)}{q}\right]_{q=(z-1)/z},\qquad r=|V(G)|-1. \] For brevity, we call this explicit composite map the \emph{Negami--Hilbert correspondence}. The underlying chromatic/characteristic-polynomial-to-broken-circuit-Hilbert-series relation is classical, and no claim of novelty is made for that underlying identity. We place the formulation in the context of works of Negami, Oxley, Whitney, Brylawski--Oxley, Proudfoot--Speyer, Llamas--Martínez-Bernal--Merino, and Berget. We then derive closed or low-degree formulas for cycles $C_n$, wheels $W_n$, complete graphs $K_n$, complete bipartite graphs $K_{m,n}$, strongly regular graphs, large-girth regular graphs, and Ramanujan graphs. Finally, as a first nontrivial construction retaining the full three-variable Negami polynomial, we equip the squarefree edge algebra of the triangle $C_3$ with the graphic-matroid rank filtration and recover the complete polynomial $f(C_3;t,x,y)$ from the bigraded Hilbert polynomial of the associated graded algebra.