Chromatic roots are dense in the whole complex plane

Abstract

I show that the zeros of the chromatic polynomials P_G(q) for the generalized theta graphs Θ^{(s,p)} are, taken together, dense in the whole complex plane with the possible exception of the disc |q-1| < 1. The same holds for their dichromatic polynomials (alias Tutte polynomials, alias Potts-model partition functions) Z_G(q,v) outside the disc |q+v| < |v|. An immediate corollary is that the chromatic zeros of not-necessarily-planar graphs are dense in the whole complex plane. The main technical tool in the proof of these results is the Beraha-Kahane-Weiss theorem on the limit sets of zeros for certain sequences of analytic functions, for which I give a new and simpler proof.

LaTeX2e, 53 pages. Version 2 includes a new Appendix B. Version 3 adds a new Theorem 1.4 and a new Section 5, and makes several small improvements. To appear in Combinatorics, Probability & Computing

References in corpus (1)

• Exact Potts Model Partition Functions on Wider Arbitrary-Length Strips of the Square Lattice

Cited by in corpus (57)

• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• The Lee-Yang and Pólya-Schur Programs. I. Linear Operators Preserving Stability
• Spanning forests and the q-state Potts model in the limit q \to 0
• A Little Statistical Mechanics for the Graph Theorist
• On the roots of all-terminal reliability polynomials
• 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
• Phase diagram of the chromatic polynomial on a torus
• The Brown-Colbourn conjecture on zeros of reliability polynomials is false
• Graph polynomials and their applications I: The Tutte polynomial
• On rational approximation of algebraic functions
• Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids
• Complex-temperature phase diagram of Potts and RSOS models
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial
• Zeros of partition functions in the NPT-ensemble
• Is the five-flow conjecture almost false?
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with special boundary conditions
• Zeros of polynomials with four-term recurrence
• Phase diagram of the triangular-lattice Potts antiferromagnet
• Classical phase transitions in a one-dimensional short-range spin model induced by entropy depletion or complex fields
• A generalized Beraha conjecture for non-planar graphs
• A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
• Exponential Time Complexity of Weighted Counting of Independent Sets
• Polynomials with rational generating functions and real zeros
• Linear bound in terms of maxmaxflow for the chromatic roots of series-parallel graphs
• Chromatic roots and limits of dense graphs
• On the Potts model partition function in an external field
• Around a Conjecture of K. Tran
• Zeros and approximations of Holant polynomials on the complex plane
• A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model
• Lower Bounds on the Ground State Entropy of the Potts Antiferromagnet on Slabs of the Simple Cubic Lattice
• On the asymptotics of the rescaled Appell polynomials
• Density of roots of the Yamada polynomial of spatial graphs
• Ground State Entropy of the Potts Antiferromagnet on Homeomorphic Expansions of Kagome Lattice Strips
• Gale duality bounds for roots of polynomials with nonnegative coefficients
• Zeros of Chromatic and Flow Polynomials of Graphs
• Semi-analytical solutions for eigenvalue problems of chains and periodic graphs
• A survey on the study of real zeros of flow polynomials
• On Hyperbolic Polynomials and Four-term Recurrence with Linear Coefficients
• On the imaginary parts of chromatic root
• Density of Zeros of the Tutte Polynomial
• On the number of clusters for planar graphs
• On uniqueness of the q-state Potts model on a self-dual family of graphs
• Exact Potts/Tutte Polynomials for Hammock Chain Graphs
• On Yamada polynomial of spatial graphs obtained by edge replacements
• Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs
• On zeros of the characteristic polynomial of matroids of bounded tree-width
• Zero Attractors of Partition Polynomials
• Tres lecciones en combinatoria algebraica. III. Arreglos de hiperplanos
• Chromatic Bounds On Orbital Chromatic Roots
• The W-polynomial and the Mahler Measure of the Kauffman Bracket
• Chromatic Zeros on the Limit $G_{\infty }^{(p,\ell )}$ of the Family $G_m^{(p,\ell )}$ of Hierarchical Graphs
• A set of chromatic roots which is dense in the complex plane and closed under multiplication by positive integers
• New expressions for order polynomials and chromatic polynomials
• Extension to the Beraha-Kahane-Weiss Theorem with Applications