Subscribe by RSS

# 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: **

*G*= (*V*,*E*), we introduce a novel invariant which we call its blowup-polynomial*p*(_{G}*n*:_{v}*v*∈*V*). To do so, we compute the determinant of the distance matrix of the graph blowup, obtained by taking*n*copies of the vertex_{v}*v*, and remove an exponential factor.- First: we show that as a function of the sizes
*n*,_{v}*p*is a polynomial, is multi-affine, and is real-stable._{G} - Second: we show that the multivariate polynomial
*p*is intimately related to the characteristic polynomial_{G}*q*of the distance matrix_{G}*D*, and that it fully recovers G whereas_{G}*q*does not._{G} - 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
*p*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._{G}

(Joint with Apoorva Khare.)