On the zeroes of hypergraph independence polynomials

MaRDI QIDQ6415795zbMATH OpenFDO

Authors David Galvin, Gwen McKinley, Will Perkins, Michail Sarantis, Prasad Tetali

Publication date 1 November 2022

Abstract: 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/(eDelta)$). Up to logarithmic factors in $Delta$ this is optimal, even for hypergraphs with all edge-sizes strictly greater than $2$. We conjecture that for $kge3$, $k$-uniform linear hypergraphs have a much larger zero-free disk of radius $Omega(Delt{a}^{-frac1k-1})$. We establish this in the case of linear hypertrees.

This page was built for publication: On the zeroes of hypergraph independence polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6415795)