Blowup-polynomials of graphs 07/15/2024

Speaker: Apoorva Khare, Indian Institute of Science
Date and time: Monday 7/15, 11am–noon
Place: Phillips 730

Abstract: Given a finite simple connected graph $G = (V,E)$ , we introduce a novel invariant which we call its blowup-polynomial $p_G(\{n_v : v in V\})$ . To do so, we compute the determinant of the distance matrix of the graph blowup, obtained by taking $n_v$ copies of the vertex $v$ , and remove an exponential factor. First: we show that as a function of the sizes $n_v$ , $p_G$ is a polynomial, is multi-affine, and is real-stable. Second: we show that the multivariate polynomial $p_G$ is intimately related to the characteristic polynomial $q_G$ of the distance matrix $D_G$ , and that it fully recovers $G$ whereas $q_G$ does not. Third: we obtain a novel characterization of the complete multi-partite graphs, as precisely those whose "homogenized" blowup-polynomials are Lorentzian/strongly Rayleigh. These results also lead to some hitherto unstudied delta-matroids. (Joint with Projesh Nath Choudhury.)