Combinatorics and Algebra Seminar- Blowup-polynomials of graphs

Title: Blowup-polynomials of graphs

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 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. First: we show 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 characterization of the complete multipartite 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.)