Asymptotic Limits and Zeros of Chromatic Polynomials and Ground State Entropy of Potts Antiferromagnets

Abstract

We study the asymptotic limiting function $W(G,q)={\lim }_{n\to \infty }P(G,q{)}^{1/n}$, where $P(G,q)$ is the chromatic polynomial for a graph $G$ with $n$ vertices. We first discuss a subtlety in the definition of $W(G,q)$ resulting from the fact that at certain special points $q_s$, the following limits do not commute: ${\lim }_{n\to \infty }{\lim }_{q\to q_s}P(G,q{)}^{1/n}\ne {\lim }_{q\to q_s}{\lim }_{n\to \infty }P(G,q{)}^{1/n}$. We then present exact calculations of $W(G,q)$ and determine the corresponding analytic structure in the complex $q$ plane for a number of families of graphs $G$, including circuits, wheels, biwheels, bipyramids, and (cyclic and twisted) ladders. We study the zeros of the corresponding chromatic polynomials and prove a theorem that for certain families of graphs, all but a finite number of the zeros lie exactly on a unit circle, whose position depends on the family. Using the connection of $P(G,q)$ with the zero-temperature Potts antiferromagnet, we derive a theorem concerning the maximal finite real point of non-analyticity in $W(G,q)$, denoted $q_c$ and apply this theorem to deduce that $q_c(sq)=3$ and $q_c(hc)=(3+\sqrt{5})/2$ for the square and honeycomb lattices. Finally, numerical calculations of $W(hc,q)$ and $W(sq,q)$ are presented and compared with series expansions and bounds.

33 pages, Latex, 5 postscript figures, published version; includes further comments on large-q series

References in corpus (9)

• Absence of Phase Transition for Antiferromagnetic Potts Models via the Dobrushin Uniqueness Theorem
• Complex-Temperature Properties of the 2D Ising Model for Nonzero Magnetic Field
• Complex-Temperature Properties of the Ising Model on 2D Heteropolygonal Lattices
• Some New Results on Complex-Temperature Singularities in Potts Models on the Square Lattice
• Ground State Entropy and the $q=3$ Potts Antiferromagnet on the Honeycomb Lattice
• Complex-Temperature Properties of the 2D Ising Model with $\beta H=\pm i\pi /2$
• Complex-Temperature Singularities in the $d=2$ Ising Model. II. Triangular Lattice
• Complex-Temperature Singularities in the $d=2$ Ising Model. III. Honeycomb Lattice
• Some New Results on Yang-Lee Zeros of the Ising Model Partition Function

Cited by in corpus (71)

• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Chromatic roots are dense in the whole complex plane
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models I. General Theory and Square-Lattice Chromatic Polynomial
• Exact Potts Model Partition Functions on Ladder Graphs
• Chromatic Polynomials for Families of Strip Graphs and their Asymptotic Limits
• Spanning forests and the q-state Potts model in the limit q \to 0
• A Little Statistical Mechanics for the Graph Theorist
• Thin Fisher Zeroes
• Lower Bounds and Series for the Ground State Entropy of the Potts Antiferromagnet on Archimedean Lattices and their Duals
• Exact Potts Model Partition Function on Strips of the Triangular Lattice
• T=0 Partition Functions for Potts Antiferromagnets on Square Lattice Strips with (Twisted) Periodic Boundary Conditions
• Chromatic Polynomials for $J(\prod H)I$ Strip Graphs and their Asymptotic Limits
• Ground State Entropy of Potts Antiferromagnets: Homeomorphic Classes with Noncompact W Boundaries
• Structural Properties of Potts Model Partition Functions and Chromatic Polynomials for Lattice Strips
• Ground State Entropy of Potts Antiferromagnets on Homeomorphic Families of Strip Graphs
• Study of the Potts Model on the Honeycomb and Triangular Lattices: Low-Temperature Series and Partition Function Zeros
• Families of Graphs with W_r({G},q) Functions That Are Nonanalytic at 1/q=0
• T=0 Partition Functions for Potts Antiferromagnets on Moebius Strips and Effects of Graph Topology
• Ground State Entropy of Potts Antiferromagnets: Cases with Noncompact W Boundaries Having Multiple Points at 1/q = 0
• Ground-State Degeneracy of Potts Antiferromagnets on Two-Dimensional Lattices: Approach Using Infinite Cyclic Strip Graphs
• Ground State Entropy of Potts Antiferromagnets and the Approach to the 2D Thermodynamic Limit
• Ground State Entropy of the Potts Antiferromagnet on Strips of the Square Lattice
• Upper and Lower Bounds for Ground State Entropy of Antiferromagnetic Potts Models
• Families of Graphs With Chromatic Zeros Lying on Circles
• Ground State Entropy of Potts Antiferromagnets: Bounds, Series, and Monte Carlo Measurements
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models II. Extended Results for Square-Lattice Chromatic Polynomial
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models III. Triangular-Lattice Chromatic Polynomial
• Ground State Entropy of the Potts Antiferromagnet on Cyclic Strip Graphs
• Ground State Entropy of Potts Antiferromagnets on Cyclic Polygon Chain Graphs
• 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
• $q$-Plane Zeros of the Potts Partition Function on Diamond Hierarchical Graphs
• Zeros of Jones Polynomials for Families of Knots and Links
• Density of states, Potts zeros, and Fisher zeros of the Q-state Potts model for continuous Q
• Complex-Temperature Partition Function Zeros of the Potts Model on the Honeycomb and Kagomé Lattices
• Potts Model Partition Functions for Self-Dual Families of Strip Graphs
• Ground State Entropy of the Potts Antiferromagnet with Next-Nearest-Neighbor Spin-Spin Couplings on Strips of the Square Lattice
• T=0 Partition Functions for Potts Antiferromagnets on Lattice Strips with Fully Periodic Boundary Conditions
• Graph polynomials and their applications I: The Tutte polynomial
• A Mapping Relating Complex and Physical Temperatures in the 2D $q$-state Potts Model and Some Applications
• Ground State Entropy of the Potts Antiferromagnet on Triangular Lattice Strips
• Distribution of complex eigenvalues for symplectic ensembles of non-Hermitian matrices
• Reliability Polynomials and their Asymptotic Limits for Families of Graphs
• Exact T=0 Partition Functions for Potts Antiferromagnets on Sections of the Simple Cubic Lattice
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial
• Zeros of the Potts Model Partition Function on Sierpinski Graphs
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with special boundary conditions
• General Structural Results for Potts Model Partition Functions on Lattice Strips
• Transfer Matrices for the Partition Function of the Potts Model on Toroidal Lattice Strips
• The 3-State Potts Antiferromagnet on the Hexagonal Lattice
• Weighted Graph Colorings
• Weighted-Set Graph Colorings
• Exact Results for Average Cluster Numbers in Bond Percolation on Lattice Strips
• Complex-q zeros of the partition function of the Potts model with long-range interactions
• Transfer Matrices for the Zero-Temperature Potts Antiferromagnet on Cyclic and Mobius Lattice Strips
• Exact Chromatic Polynomials for Toroidal Chains of Complete Graphs
• Large-q series expansion for the ground state degeneracy of the q-state Potts antiferromagnet on the (3.12^2) lattice
• Chromatic polynomials of random graphs
• Asymptotic Behavior of Acyclic and Cyclic Orientations of Directed Lattice Graphs
• Study of Exponential Growth Constants of Directed Heteropolygonal Archimedean Lattices
• The Structure of Chromatic Polynomials of Planar Triangulation Graphs and Implications for Chromatic Zeros and Asymptotic Limiting Quantities
• Partition Function Zeros of a Restricted Potts Model on Lattice Strips and Effects of Boundary Conditions
• Lower Bounds on the Ground State Entropy of the Potts Antiferromagnet on Slabs of the Simple Cubic Lattice
• End Graph Effects on Chromatic Polynomials for Strip Graphs of Lattices and their Asymptotic Limits
• Ground State Entropy of the Potts Antiferromagnet on Homeomorphic Expansions of Kagome Lattice Strips
• Partition Function Zeros of a Restricted Potts Model on Self-Dual Strips of the Square Lattice
• Potts Partition Function Zeros and Ground State Entropy on Hanoi Graphs
• Improved Lower Bounds on the Ground-State Entropy of the Antiferromagnetic Potts Model
• Ground State Entropy in Potts Antiferromagnets and Chromatic Polynomials
• Chromatic Zeros on the Limit $G_{\infty }^{(p,\ell )}$ of the Family $G_m^{(p,\ell )}$ of Hierarchical Graphs
• Exact Potts/Tutte Polynomials for Hammock Chain Graphs
• Jones Polynomials and their Zeros for a Family of Knots and Links