#####
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 *p*_{G}({*n*_{v} : *v*∈*V*}).
This is obtained by dividing the determinant of the distance matrix of
its blowup graph *G*[**n**] (containing *n*_{v} copies of *v*) by an
exponential factor. We show that *p*_{G}(**n**) is indeed a polynomial
function in the sizes *n*_{v}, 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 *p*_{G} being completely/strongly log-concave,
i.e., Lorentzian. (These results extend to weighted graphs.)
Finally, we show *p*_{G} is indeed a graph invariant, \textit{i.e.}, *p*_{G} 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: