Deterministic approximate counting of colorings with fewer than $2\Delta$ colors via absence of zeros
<|reference_start|>Deterministic approximate counting of colorings with fewer than $2\Delta$ 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$.<|reference_end|>
@article{bencs2024deterministic,
    title={Deterministic approximate counting of colorings with fewer than
  $2\Delta$ colors via absence of zeros},
    author={Ferenc Bencs, Khallil Berrekkal, Guus Regts},
    journal={arXiv preprint arXiv:2408.04727},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.04727},
    primaryClass={math.CO cs.DM cs.DS}
}