On the Zeroes of Hypergraph Independence Polynomials

Start Date: November 27, 2023
Event Start Time: 2:00 PM
Event End Time: 3:00 PM
Seminar Series: Rutgers Discrete Mathematics Seminar
Presenter(s): Michail Sarantis - Carnegie Mellon University
Event Location: Conference Room 705 | Rutgers University | Hill Center | 110 Frelinghuysen Rd
Event Additional Info: <p>See: <a href="https://sites.google.com/view/rutgersdmseminar">https://sites.google.com/view/rutgersdmseminar</a></p>
Presentation Type: Stand Alone Presentation
Abstract:
We prove that the multivariate independence polynomial of any hypergraph of maximum degree $\Delta$ has no zeroes on the complex polydisc of radius $\sim\frac{1}{e\Delta}$, 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.

Events