Ground state entropy in Potts antiferromagnets

The q-state Potts antiferromagnet exhibits nonzero ground state entropy S0({G},q)≠0 for sufficiently large q on a given n-vertex lattice Λ or graph G and its n→∞ limit {G}. We present exact calculations of the zero-temperature partition function Z(G,q,T=0) and W({G},q), where S0=kBlnW, for this model on a number of families G. These calculations have interesting connections with graph theory, since Z(G,q,T=0)=P(G,q), where the chromatic polynomial P(G,q) gives the number of ways of coloring the vertices of the graph G such that no adjacent vertices have the same color. Generalizing q from Z to C, we determine the accumulation set B of the zeros of P(G,q), which constitute the continuous loci of points on which W is nonanalytic. The Potts antiferromagnet has a zero-temperature critical point at the maximal value qc where B crosses the real q-axis. In particular, exact solutions for W and B are given for infinitely long, finite-width strips of various lattices; in addition to their intrinsic interest, these yield insight into the approach to the 2D thermodynamic limit. Some corresponding results are presented for the exact finite-temperature Potts free energy on families of graphs. Finally, we present rigorous upper and lower bounds on W for 2D lattices.