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.

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