Séminaire Lotharingien de Combinatoire, 86B.42 (2022), 12 pp.

Projesh Nath Choudhury and Apoorva Khare

Blowup Polynomials and delta-Matroids of Graphs

Abstract. For every finite simple connected graph G = (V,E), we introduce an invariant, its blowup-polynomial pG({nv : vV}). This is obtained by dividing the determinant of the distance matrix of its blowup graph G[n] (containing nv copies of v) by an exponential factor. We show that pG(n) is indeed a polynomial function in the sizes nv, which is moreover multi-affine and real-stable. This associates a hitherto unexplored delta-matroid to each graph G; and we provide a second novel one for each tree. We also obtain a new characterization of complete multipartite graphs, via the homogenization at -1 of pG being completely/strongly log-concave, i.e., Lorentzian. (These results extend to weighted graphs.) Finally, we show pG is indeed a graph invariant, \textit{i.e.}, pG and its symmetries (in the variables n) recover G and its isometries, respectively.

Received: November 25, 2021. Accepted: March 4, 2022. Final version: April 1, 2022.

The following versions are available: