Families of Graphs with W_r({G},q) Functions That Are Nonanalytic at 1/q=0

Abstract

Denoting $P(G,q)$ as the chromatic polynomial for coloring an $n$-vertex graph $G$ with $q$ colors, and considering the limiting function $W(\{G\},q)={\lim }_{n\to \infty }P(G,q{)}^{1/n}$, a fundamental question in graph theory is the following: is $W_r(\{G\},q)=q^{-1}W(\{G\},q)$ analytic or not at the origin of the $1/q$ plane? (where the complex generalization of $q$ is assumed). This question is also relevant in statistical mechanics because $W(\{G\},q)=\exp (S_0/k_B)$, where $S_0$ is the ground state entropy of the $q$-state Potts antiferromagnet on the lattice graph $\{G\}$, and the analyticity of $W_r(\{G\},q)$ at $1/q=0$ is necessary for the large-$q$ series expansions of $W_r(\{G\},q)$. Although $W_r$ is analytic at $1/q=0$ for many $\{G\}$, there are some $\{G\}$ for which it is not; for these, $W_r$ has no large-$q$ series expansion. It is important to understand the reason for this nonanalyticity. Here we give a general condition that determines whether or not a particular $W_r(\{G\},q)$ is analytic at $1/q=0$ and explains the nonanalyticity where it occurs. We also construct infinite families of graphs with $W_r$ functions that are non-analytic at $1/q=0$ and investigate the properties of these functions. Our results are consistent with the conjecture that a sufficient condition for $W_r(\{G\},q)$ to be analytic at $1/q=0$ is that $\{G\}$ is a regular lattice graph $\Lambda$. (This is known not to be a necessary condition).

22 pages, Revtex, 4 encapsulated postscript figures, to appear in Phys. Rev. E

References in corpus (3)

• 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

Cited by in corpus (35)

• 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
• Chromatic Polynomials for Families of Strip Graphs and their Asymptotic Limits
• Thin Fisher Zeroes
• A Little Statistical Mechanics for the Graph Theorist
• Lower Bounds and Series for the Ground State Entropy of the Potts Antiferromagnet on Archimedean Lattices and their Duals
• 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
• Ground State Entropy of Potts Antiferromagnets: Cases with Noncompact W Boundaries Having Multiple Points at 1/q = 0
• Ground State Entropy of Potts Antiferromagnets and the Approach to the 2D Thermodynamic Limit
• Ground-State Degeneracy of Potts Antiferromagnets on Two-Dimensional Lattices: Approach Using Infinite Cyclic Strip Graphs
• Ground State Entropy of the Potts Antiferromagnet on Strips of the Square Lattice
• 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
• Zeros of Jones Polynomials for Families of Knots and Links
• Complex-Temperature Partition Function Zeros of the Potts Model on the Honeycomb and Kagomé Lattices
• Ground State Entropy of the Potts Antiferromagnet with Next-Nearest-Neighbor Spin-Spin Couplings on Strips of the Square Lattice
• Potts Model Partition Functions for Self-Dual Families of Strip Graphs
• Graph polynomials and their applications I: The Tutte polynomial
• Ground State Entropy of the Potts Antiferromagnet on Triangular Lattice Strips
• General Structural Results for Potts Model Partition Functions on Lattice Strips
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with special boundary conditions
• 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
• The Structure of Chromatic Polynomials of Planar Triangulation Graphs and Implications for Chromatic Zeros and Asymptotic Limiting Quantities
• Lower Bounds on the Ground State Entropy of the Potts Antiferromagnet on Slabs of the Simple Cubic Lattice
• Improved Lower Bounds on the Ground-State Entropy of the Antiferromagnetic Potts Model
• Ground State Entropy in Potts Antiferromagnets and Chromatic Polynomials
• Exact Potts/Tutte Polynomials for Hammock Chain Graphs
• Chromatic Zeros on the Limit $G_{\infty }^{(p,\ell )}$ of the Family $G_m^{(p,\ell )}$ of Hierarchical Graphs