Blowup Polynomials and Delta-matroids of Graphs

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. In this talk, we first see 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 characterisation of the complete multipartite graphs, precisely those whose "homogenised" blowup polynomials are Lorentzian/strongly Rayleigh. Finally, we explain how to obtain from p_G a novel delta-matroid for every graph; we also provide a second deltamatroid for every tree, which too is hitherto unexplored, but whose construction does not extend to all graphs.