Michail Sarantis, Carnegie Mellon University

Abstract

We prove that the multivariate independence polynomial of any hypergraph of maximum degree $Delta$ has no zeroes on the complex polydisc of radius $simfrac{1}{eDelta}$, centered at the origin. Up to logarithmic factors in $Delta$, the result is optimal, even for graphs with all edge sizes greater than $2$. As a corollary, we get an FPTAS for approximating the independence polynomial in this region of the complex plane.

We furthermore prove the corresponding radius for the $k$-uniform linear hypertrees is $Omega(Delta^{-1/(k-1)})$, a significant discrepancy from the graph case.

Joint work with David Galvin, Gwen McKinley, Will Perkins and Prasad Tetali. 

See: https://sites.google.com/view/rutgersdmseminar