We study the locations of complex zeros 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 Δ have a zero-free disk almost as large as the optimal disk for graphs of maximum degree Δ established by Shearer (of radius ~ 1/(e Δ)). Up to logarithmic factors in Δ this is optimal, even for hypergraphs with all edge-sizes strictly greater than 2. We conjecture that for k ≥ 3, there exist families of k-uniform linear hypergraphs that have a much larger zero-free disk of radius Ω(Δ^{-1/(k-1)}). We establish this in the case of linear hypertrees.

Discrete Math Seminar

Friday, January 27, 2023

11:00am

WXLR A113

Michail Sarantis

PhD Student

Carnegie Mellon University