Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros

Let Δ,q≥ 3 be integers. We prove that there exists η≥ 0.002 such that if q≥ (2-η)Δ, then there exists an open set U⊂ C 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-η)Δ. 41 pages. This is the TheoretiCS journal version