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 : v∈V}).
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: