
Department Colloquium
Fri., Jul. 14, 2023 3:30 p.m.
Location: RIC 208
Speaker: Projesh Nath Choudhury, IIT Gandhinagar
Title: Blowup-polynomials of graphs (102 kB)
Abstract:
- First: we show that as a function of the sizes nv, pG is a polynomial, is multi-affine, and is real-stable.
- Second: we show that the multivariate polynomial pG is intimately related to the characteristic polynomial qG of the distance matrix DG, and that it fully recovers G whereas qG 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.
- Finally: we show how to obtain from pG a novel delta-matroid for every graph. We also provide a second delta-matroid for every tree, which too is hitherto unexplored, but whose construction does not extend to all graphs.
(Joint with Apoorva Khare.)