论文标题
在超图独立性多项式的零上
On the zeroes of hypergraph independence polynomials
论文作者
论文摘要
我们研究有界程度超图的独立性多项式复杂零的位置。对于图，这是一个长期研究的主题，在统计物理学，算法和组合术中应用。有界度图的无零区域的结果包括最佳无零磁盘上的Shearer结果，以及其他无零区域的最新结果。少得多的超图已知。我们通过证明所有最大程度$δ$的无零磁盘的无零磁盘的最大磁盘与最高度$δ$的最佳磁盘一样大，从而对有限度的超gaphs进行一些步骤，以了解有界度的超级gaphs。在$δ$中以对数因素为止，这是最佳的，即使对于所有边缘尺寸的超图严格大于$ 2 $。我们推测，对于$ k \ ge 3 $，$ k $ - 均匀的线性超图具有更大的零零磁盘的半径$ω（δ^^{ - \ frac {1} {1} {k-1}}）$。我们在线性大型的情况下确定了这一点。
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 $Δ$ have a zero-free disk almost as large as the optimal disk for graphs of maximum degree $Δ$ established by Shearer (of radius $\sim 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\ge 3$, $k$-uniform linear hypergraphs have a much larger zero-free disk of radius $Ω(Δ^{- \frac{1}{k-1}} )$. We establish this in the case of linear hypertrees.
