Multivariate blowup-polynomials of graphs

Authors Projesh Nath Choudhury, Apoorva Khare

Publication date 7 June 2021

Graph polynomials (05C31) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15) Real polynomials: location of zeros (26C10)

Abstract: In recent joint work (2021), we introduced a novel multivariate polynomial attached to every metric space - in particular, to every finite simple connected graph

G

- and showed it has several attractive properties. First, it is multi-affine and real-stable (leading to a hitherto unstudied delta-matroid for each graph

G

). Second, the polynomial specializes to (a transform of) the characteristic polynomial

c h i_{D_{G}}

of the distance matrix

D_{G}

; as well as recovers the entire graph, where

c h i_{D_{G}}

cannot do so. Third, the polynomial encodes the determinants of a family of graphs formed from

G

, called the blowups of

G

. In this short note, we exhibit the applicability of these tools and techniques to other graph-matrices and their characteristic polynomials. As a particular case, we will see that the adjacency characteristic polynomial

c h i_{A_{G}}

is in fact the shadow of a richer multivariate blowup-polynomial, which is similarly multi-affine and real-stable. Moreover, this polynomial encodes not only the aforementioned three properties, but also yields additional information for specific families of graphs.

This page was built for publication: Multivariate blowup-polynomials of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6369668)