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 , we introduce a novel invariant which we call its blowup-polynomial
. To do so, we compute the determinant of the distance matrix of the graph blowup, obtained by taking
copies of the vertex
, and remove an exponential factor. First: we show that as a function of the sizes
,
is a polynomial, is multi-affine, and is real-stable. Second: we show that the multivariate polynomial
is intimately related to the characteristic polynomial
of the distance matrix
, and that it fully recovers
whereas
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.)