Structural properties of Potts model partition functions and chromatic polynomials for lattice strips

The q-state Potts model partition function (equivalent to the Tutte polynom ial) for a lattice strip of fixed width L-y and arbitrary length L-x has th e form Z(G, q, v) = Sigma (NZ,j)(j=1) c(Z,G,j)(lambda (Z,G,j))(Lx), where L ; is a temperature-dependent variable. The special case of the zero-tempera ture antiferromagnet (v = -1) is the chromatic polynomial P(G, q). Using co loring and transfer matrix methods, we give general formulas for C-X,C-G = Sigma (NX,j)(j=1) c(X,G,j) for X = Z,P on cyclic and Mobius strip graphs of the square and triangular lattice. Combining these with a general expressi on for the (unique) coefficient c(Z,G,j) of degree d in q: c((d)) = U-2d(ro otq/2), where U-n(x) is the Chebyshev polynomial of the second kind, we det ermine the number of lambda (Z,G,j)'s with coefficient c((d)) in Z(G,q,v) f or these cyclic strips of width L-y to be n(Z)(L-y,d)=(2d + 1)(L-y + d + 1) (-1) ((2Lx)(Ly-d)) for 0 less than or equal to d less than or equal to L-y and zero otherwise, For both cyclic and Mobius strips of these lattices, th e total number of distinct eigenvalues lambda (Z,G,j) is calculated to be N -Z,N-L,N-lambda=((2Lx)(Ly)). Results are also presented for the analogous n umbers n(P)(L-y, d) and N(P,Ly,)lambda for P(G,q). We find that n(P)(L-y, 0 )=n(P)(L-y- 1,1)=MLx-1 (Motzkin number), n(Z)(L-y,0)= C-Lx (the Catalan num ber), and give an exact expression for N-P,N-Ly,N-lambda. Our results for N -Z,N-Ly,N-lambda and N-P,N-Ly,N-lambda apply for both the cyclic and Mobius strips of both the square and triangular lattices; we also point out the i nteresting relations N-Z,N-Ly,N-lambda = 2N(DA,tri.Ly) and N-P,N-Ly,N-lambd a = 2N(DA,sq,Ly,) where N-DA,N-A,N-n denotes the number of directed lattice animals on the lattice Lambda. We find the asymptotic growths N-Z,N-Ly,N-l ambda similar to L-y(-1.2) 4(Ly) and N-P,N-Ly,N-lambda similar to L(y)(-1.2 )3(Ly) as L-y --> infinity. Some general geometric identities for Potts mod el partition functions are also presented. 0 2001 Published by Elsevier Sci ence B.V.