2024/08/08 by Bencs, Ferenc, Berrekkal, Khallil, Regts, Guus · 2 citations
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2408.04727
Let Δ,q≥ 3 be integers. We prove that there exists η≥ 0.002 such that if q≥ (2-η)Δ, then there exists an open set U⊂ ℂ that contains the interval [0,1] such that for each w∈ U and any graph G=(V,E) of maximum degree at most Δ, the partition function of the anti-ferromagnetic q-state Potts model evaluated at w does not vanish. This provides a (modest) improvement on a result of Liu, Sinclair, and Srivastava, and breaks the q=2Δ-barrier for this problem. As a direct consequence we obtain via Barvinok's interpolation method a deterministic polynomial time algorithm to approximate the number of proper q-colorings of graphs of maximum degree at most Δ, provided q≥ (2-η)Δ.