On the zeroes of hypergraph independence polynomials

Combinatorics Seminar
Wednesday, March 8, 2023 - 4:00pm for 1 hour (actually 50 minutes)
C457 Classroom Van Leer
Michail Sarantis – Carnegie Mellon University
Anton Bernshteyn

We study the locations of complex zeroes of independence polynomials of bounded degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free regions for bounded-degree graphs include Shearer's result on the optimal zero-free disk, along with several recent results on other zero-free regions. Much less is known for hypergraphs. We make some steps towards an understanding of zero-free regions for bounded-degree hypergaphs by proving that all hypergraphs of maximum degree $\Delta$ have a zero-free disk almost as large as the optimal disk for graphs of maximum degree $\Delta$ established by Shearer (of radius $\sim1/(e\Delta)$). Up to logarithmic factors in $\Delta$ this is optimal, even for hypergraphs with all edge-sizes strictly greater than $2$. We conjecture that for $k\geq 3$, there exist families of $k$-uniform linear hypergraphs that have a much larger zero-free disk of radius $\Omega(\Delta^{-1/(k-1)})$. We establish this in the case of linear hypertrees. Joint work with David Galvin, Gwen McKinley, Will Perkins and Prasad Tetali.