Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions

Abstract

I show that there exist universal constants $C(r)<\infty$ such that, for all loopless graphs $G$ of maximum degree $\le r$, the zeros (real or complex) of the chromatic polynomial $P_G(q)$ lie in the disc $|q|<C(r)$. Furthermore, $C(r)\le \mathrm{7.963906...}r$. This result is a corollary of a more general result on the zeros of the Potts-model partition function $Z_G(q,v_e)$ in the complex antiferromagnetic regime $|1+v_e|\le 1$. The proof is based on a transformation of the Whitney-Tutte-Fortuin-Kasteleyn representation of $Z_G(q,v_e)$ to a polymer gas, followed by verification of the Dobrushin-Kotecký-Preiss condition for nonvanishing of a polymer-model partition function. I also show that, for all loopless graphs $G$ of second-largest degree $\le r$, the zeros of $P_G(q)$ lie in the disc $|q|<C(r)+1$. Along the way, I give a simple proof of a generalized (multivariate) Brown-Colbourn conjecture on the zeros of the reliability polynomial for the special case of series-parallel graphs.

arXiv comment47 pages (LaTeX). Revised version contains slightly simplified proofs of Propositions 4.2 and 4.5. Version 3 fixes a silly error in my proof of Proposition 4.1, and adds related discussion. To appear in Combinatorics, Probability & Computing

Cited by in corpus (48)

• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Homogeneous multivariate polynomials with the half-plane property
• Cluster expansion for abstract polymer models. New bounds from an old approach
• Abstract cluster expansion with applications to statistical mechanical systems
• Spanning forests and the q-state Potts model in the limit q \to 0
• A Little Statistical Mechanics for the Graph Theorist
• Complex zero-free regions at large |q| for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
• Partition function zeros at first-order phase transitions: A general analysis
• Cluster simulations of loop models on two-dimensional lattices
• The Brown-Colbourn conjecture on zeros of reliability polynomials is false
• On the convergence of cluster expansions for polymer gases
• Complex-Temperature Phase Diagrams for the q-State Potts Model on Self-Dual Families of Graphs and the Nature of the $q\to \infty$ Limit
• Convergence of Mayer and Virial expansions and the Penrose tree-graph identity
• Zeros of Jones Polynomials for Families of Knots and Links
• Potts Model Partition Functions for Self-Dual Families of Strip Graphs
• Dynamic critical behavior of the Chayes-Machta-Swendsen-Wang algorithm
• Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids
• Reliability Polynomials and their Asymptotic Limits for Families of Graphs
• The Tutte-Potts connection in the presence of an external magnetic field
• Extremes of the internal energy of the Potts model on cubic graphs
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial
• Continuos particles in the Canonical Ensemble as an abstract polymer gas
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with special boundary conditions
• Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
• Correlation decay and partition function zeros: Algorithms and phase transitions
• Abstract polymer models with general pair interactions
• A generalized Beraha conjecture for non-planar graphs
• Linear bound in terms of maxmaxflow for the chromatic roots of series-parallel graphs
• Clustering Bounds on N-Point Correlations for Unbounded Spin Systems
• Onsager's missing steps retraced
• Surface transitions of the semi-infinite Potts model I: the high bulk temperature regime
• Weighted Graph Colorings
• Weighted-Set Graph Colorings
• Transfer Matrices for the Zero-Temperature Potts Antiferromagnet on Cyclic and Mobius Lattice Strips
• Chromatic roots and limits of dense graphs
• Measures of Spin Ordering in the Potts Model with a Generalized External Magnetic Field
• Exact Chromatic Polynomials for Toroidal Chains of Complete Graphs
• On the Potts model partition function in an external field
• Absence of zeros implies strong spatial mixing
• Absence of phase transitions in a class of integer spin systems
• Counting Complex Disordered States by Efficient Pattern Matching: Chromatic Polynomials and Potts Partition Functions
• Improved Lower Bounds on the Ground-State Entropy of the Antiferromagnetic Potts Model
• The number of link and cluster states: the core of the 2D $q$ state Potts model
• Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence
• The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra
• Potts Partition Function Zeros and Ground State Entropy on Hanoi Graphs
• A note on the shameful conjecture
• On zeros of the characteristic polynomial of matroids of bounded tree-width