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

Let $\Delta, q \geq 3$ be integers. We prove that there exists $\eta \geq 0.002$ such that if $q \geq (2 - \eta)\Delta$, then there exists an open set $\mathcal{U} \subset \mathbb{C}$ that contains the interval $[0, 1]$ such that for each $w \in \mathcal{U}$ and any graph $G = (V, E)$ of maximum degree at most $\Delta$, 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\Delta$-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 $\Delta$, provided $q \geq (2 - \eta)\Delta$.

• View at Publisher

Free Full Text ( Final Version , 565kb )