Zero-Free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime

We show that for 𝑞-colorings in 𝑘-uniform hypergraphs with maximum degree Δ, if 𝑘 ≥ 50 and 𝑞 ≥ 700Δ 5 𝑘 -10 , there is a "Lee-Yang" zero-free strip around the interval [0, 1] of the partition function, which includes the special case of uniform enumeration of hypergraph colorings. As an immediate consequence, we obtain Berry-Esseen type inequalities for hypergraph 𝑞-colorings under such conditions, demonstrating the asymptotic normality for the size of any color class in a uniformly random coloring. Our framework also extends to the study of "Fisher zeros", leading to deterministic algorithms for approximating the partition function in the zero-free region.

Our approach is based on extending the recent work of [Liu, Wang, Yin, Yu, STOC 2025] to general constraint satisfaction problems (CSP). We focus on partition functions defined for CSPs by introducing external fields to the variables. A key component in our approach is a projection-lifting scheme, which enables us to essentially lift information percolation type analysis for Markov chains from the real line to the complex plane. Last but not least, we also show a Chebyshev-type inequality under the sampling LLL condition for atomic CSPs.